ZOJ3496|ZOJ3496 Assignment ZOJ3496Assignment

传送门
这题也是真恶心……
题目大意是俩公司要运货，每条路有容量上限。然后B公司手里有p个……（技能点？）如果在一条路上放了x个技能点，这条路经过了y个货物，那么B公司就会收x*y的钱。现在要求的是，B公司最大获利和A公司在付费最大时的最小值，和这个问题完全倒过来。
首先有一个结论是B公司一定会把所有技能点一股脑全放在流量最大的那条边上。（贪心显然）注意是当前图上的流量而不是原图容量。那么这个问题就转化成了有上/下界限制的最大最小流。对于第一个问题，我们二分一个流的上界，首先判断这个其实就相当于一个正常的网络流，直接跑dinic即可，然后记录一下是否与一开始跑出来的值是相等的，这样二分求最大值即可。（答案就是当前容量上限的最大值*p）
而对于第二个问题，我们二分流的下界。这个时候就是一个有上下界的网络流，要建立辅助源汇点那一套跑流。不过具体的二分操作依然没变。注意的是，如果在二分过程中，当前的下届大于原来的上界，就直接返回0.最后我们求出最小的下界，然后用它乘以p来更新答案。
【ZOJ3496|ZOJ3496 Assignment】但是这题坑点很多的……首先是因为这题重构图很多，注意不能大量用memset。还有就是在head复制的时候不要复制少了，辅助源汇点编号不要小了（因为这题S，T）是给定的……，还有就是这次在判断最小流的时候……删除辅助源汇点最稳妥的做法是把其head设为-1，这样可以保证不会跑到。（不知道为啥，这次如果像以前一样把源汇点直接连的边设为不可走会GG……）
看一下代码吧。

#include #include #include #include #include #include #include #include #include #define rep(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define enter putchar('\n') #define fr friend inline #define y1 poj #define mp make_pair #define pr pair #define fi first #define sc second #define pb push_back #define I puts("Oops")using namespace std; typedef long long ll; const int M = 605; const int N = 40005; const ll INF = 1e14; const double eps = 1e-7; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar(); return ans * op; }struct edge { ll next,to,from,v; }e[N<<1]; ll Ti,head[M],cur[M],deg[M],x[N],y[N],z[N],n,m,g,ecnt = -1,S,T,S1,T1,tot,p; ll dep[M],maxn,st,ed; queue q; void add(int x,int y,ll z) { e[++ecnt].to = y; e[ecnt].next = head[x]; e[ecnt].v = z; head[x] = ecnt; }bool bfs(int s,int t) { while(!q.empty()) q.pop(); rep(i,0,n+3) cur[i] = head[i]; memset(dep,-1,sizeof(dep)); dep[s] = 0,q.push(s); while(!q.empty()) { int k = q.front(); q.pop(); for(int i = head[k]; ~i; i = e[i].next) { if(e[i].v && dep[e[i].to] == -1) dep[e[i].to] = dep[k] + 1,q.push(e[i].to); } } return dep[t] != -1; }ll dfs(int s,int t,ll lim) { if(s == t || !lim) return lim; ll flow = 0; for(int i = cur[s]; ~i; i = e[i].next) { cur[s] = i; if(dep[e[i].to] != dep[s] + 1) continue; ll f = dfs(e[i].to,t,min(lim,e[i].v)); if(f) { e[i].v -= f,e[i^1].v += f; flow += f,lim -= f; if(!lim) break; } } if(!flow) dep[s] = -1; return flow; }ll dinic(int s,int t) { ll maxflow = 0; while(bfs(s,t)) maxflow += dfs(s,t,INF); return maxflow; }bool checkmax(ll k) { memset(head,-1,sizeof(head)),ecnt = -1; rep(i,1,m) add(x[i],y[i],min(k,z[i])),add(y[i],x[i],0); ll now = dinic(S,T); return now == g; }ll solvemax() { ll L = 0,R = maxn,cur = 0; while(L <= R) { ll mid = (L+R) >> 1; if(checkmax(mid)) cur = mid,R = mid - 1; else L = mid + 1; } return cur * p; }bool checkmin(ll k) { memset(head,-1,sizeof(head)),memset(deg,0,sizeof(deg)); ecnt = -1,tot = 0; rep(i,1,m) { if(z[i] < k) return 0; add(x[i],y[i],z[i] - k),add(y[i],x[i],0); deg[x[i]] += k,deg[y[i]] -= k; } S1 = n + 1,T1 = S1 + 1; rep(i,1,n) { if(deg[i] < 0) add(S1,i,-deg[i]),add(i,S1,0); else add(i,T1,deg[i]),add(T1,i,0),tot += deg[i]; } add(T,S,INF),add(S,T,0); ll now = dinic(S1,T1); if(now != tot) return 0; head[S1] = head[T1] = -1; ll cur = dinic(S,T); return cur == g; }ll solvemin() { ll L = 0,R = maxn,cur = 0; while(L <= R) { ll mid = (L+R) >> 1; if(checkmin(mid)) cur = mid,L = mid + 1; else R = mid - 1; } return cur * (ll)p; }int main() { Ti = read(); while(Ti--) { n = read(),m = read(),S = read() + 1,T = read() + 1,p = read(); memset(head,-1,sizeof(head)),maxn = 0,ecnt = -1; rep(i,1,m) { x[i] = read() + 1,y[i] = read() + 1,z[i] = read(); add(x[i],y[i],z[i]),add(y[i],x[i],0),maxn = max(maxn,z[i]); } g = dinic(S,T); printf("%lld ",solvemax()); printf("%lld\n",solvemin()); } return 0; }

转载于:https://www.cnblogs.com/captain1/p/10134851.html