差别

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

--- 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>
 \\
+==== 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 ====

CVBB ACM Team

用户工具

站点工具

差别

页面工具