用户工具

站点工具


2020-2021:teams:wangzai_milk:20200712比赛记录

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
2020-2021:teams:wangzai_milk:20200712比赛记录 [2020/07/15 13:14]
zars19 [A - B-Suffix Array]
2020-2021:teams:wangzai_milk:20200712比赛记录 [2020/07/16 15:15] (当前版本)
wzx27
行 316: 行 316:
 </​code></​hidden>​ </​code></​hidden>​
 \\ \\
 +
 +==== H - Minimum-cost Flow ==== 
 +
 +费用流建图,每条边的费用已知,容量在每次询问时给出,每次询问求流出 $1$ 单位的最小费用。
 +
 +可以先假设每条边容量为 $1$ ,每次给出具体容量时再做调整。
 +具体做的时候不知道哪里被卡了一直 $t$ ,改了很久才过(快读+dij费用流)。
 +
 +<hidden code> <code cpp>
 +#pragma GCC optimize(3,"​Ofast","​inline"​)
 +#​include<​bits/​stdc++.h>​
 +#define ALL(x) (x).begin(),​(x).end()
 +#define ll long long
 +#define ull unsigned long long
 +#define pii_ pair<​int,​int>​
 +#define mp_ make_pair
 +#define pb push_back
 +#define fi first
 +#define se second
 +#define rep(i,a,b) for(int i=(a);​i<​=(b);​i++)
 +#define per(i,a,b) for(int i=(a);​i>​=(b);​i--)
 +#define show1(a) cout<<#​a<<"​ = "<<​a<<​endl
 +#define show2(a,b) cout<<#​a<<"​ = "<<​a<<";​ "<<#​b<<"​ = "<<​b<<​endl
 +using namespace std;
 +const ll INF = 1LL<<​60;​
 +const int inf = 1<<​30;​
 +const int maxn = 2005;
 +inline void fastio() {ios::​sync_with_stdio(false);​cin.tie(0);​cout.tie(0);​}
 +inline int read(){
 +   int s=0,w=1;
 +   char ch=getchar();​
 +   ​while(ch<'​0'​||ch>'​9'​){if(ch=='​-'​)w=-1;​ch=getchar();​}
 +   ​while(ch>​='​0'&&​ch<​='​9'​) s=s*10+ch-'​0',​ch=getchar();​
 +   ​return s*w;
 +}
 +ll gcd(ll a,ll b) {return b==0?​a:​gcd(b,​a%b);​}
 +ll sum[maxn];
 +int n,m,q,num;
 +int head[maxn],​dis[maxn],​h[maxn],​PrePoint[maxn],​PreEdge[maxn];​
 +vector<​int>​ mcost;
 +struct node
 +{
 +    int u,​v,​f,​w,​nxt;​
 +}edge[maxn];​
 +inline void addedge(int x,int y,int f,int z)
 +{
 +    edge[num].u=x;​
 +    edge[num].v=y;​
 +    edge[num].f=f;​
 +    edge[num].w=z;​
 +    edge[num].nxt=head[x];​
 +    head[x]=num++;​
 +}
 +void add(int u,int v,int w,int c)
 +{
 +    addedge(u,​v,​w,​c);​
 +    addedge(v,​u,​0,​-c);​
 +}
 +int MCMF(int s,int t)
 +{
 +    int ansflow=0;
 +    rep(i,1,n) h[i] = 0;
 +    while(1)
 +    {
 +        priority_queue<​pii_>​q;​
 +        rep(i,1,n) dis[i] = inf;
 +        dis[s]=0;
 +        q.push(make_pair(0,​s));​
 +        while(q.size()!=0)
 +        {
 +            pii_ p=q.top();​q.pop();​
 +            if(-p.fi!=dis[p.se]) continue;
 +            if(p.se==t) break;
 +            for(int i=head[p.se];​i!=-1;​i=edge[i].nxt)
 +            {
 +                int nowcost=edge[i].w+h[p.se]-h[edge[i].v];​
 +                if(edge[i].f>​0&&​dis[edge[i].v]>​dis[p.se]+nowcost)
 +                {
 +                    dis[edge[i].v]=dis[p.se]+nowcost;​
 +                    q.push(make_pair(-dis[edge[i].v],​edge[i].v));​
 +                    PrePoint[edge[i].v]=p.se;​
 +                    PreEdge[edge[i].v]=i;​
 +                }
 +            }
 +        }
 +        if(dis[t]==inf) break;
 +        for(int i=1;​i<​=n;​i++) h[i]+=dis[i];​
 +        int nowflow=inf;​
 +        for(int now=t;​now!=s;​now=PrePoint[now])
 +            nowflow=min(nowflow,​edge[PreEdge[now]].f);​
 +        for(int now=t;​now!=s;​now=PrePoint[now])
 +            edge[PreEdge[now]].f-=nowflow,​
 +            edge[PreEdge[now]^1].f+=nowflow;​
 +        ansflow+=nowflow;​
 +        mcost.pb(h[t]);​
 +    }
 +    return ansflow;;
 +}
 +int main()
 +{
 +    //fastio();
 +    ll u,v,c;
 +    while(~scanf("​%d%d",&​n,&​m)){
 +        rep(i,1,n) head[i] = -1;
 +        num = 2;
 +        mcost.clear();​
 +        int s = 1,t = n;
 +        rep(i,1,m){
 +            u = read();
 +            v = read();
 +            c = read();
 +            add(u,​v,​1,​c);​
 +        }
 +        int maxflow = MCMF(s,t);
 +        sort(ALL(mcost));​
 +        //for(int x:mcost) show1(x);
 +        int sz = mcost.size();​
 +        rep(i,1,sz) sum[i] = sum[i-1] + mcost[i-1];
 +        int q = read();
 +        while(q--){
 +            u = read();v = read();
 +            if(u*maxflow<​v) printf("​NaN\n"​);​
 +            else{
 +                int L = 1,R = sz,pos;
 +                while(L<​=R){
 +                    int mid = (L+R)>>​1;​
 +                    if(u*mid >= v) pos = mid,​R=mid-1;​
 +                    else L = mid+1;
 +                } //​show1(pos);​
 +                ll a = u*sum[pos-1];​
 +                ll o = (v-u*(pos-1)) * (sum[pos] - sum[pos-1]);​ //​show2(a,​o);​
 +                a = a+o;
 +                ll g = gcd(a,v);
 +                a /= g, v /= g;
 +                printf("​%lld/​%lld\n",​a,​v);​
 +            }
 +        }
 +    }
 +    return 0;
 +}
 +</​code>​ <​hidden>​
 +\\
 +
 ==== J - Easy Integration ==== ==== J - Easy Integration ====
  
2020-2021/teams/wangzai_milk/20200712比赛记录.1594790093.txt.gz · 最后更改: 2020/07/15 13:14 由 zars19