ZOJ3496 Assignment

这题也是真恶心……

题目大意是俩公司要运货，每条路有容量上限。然后B公司手里有p个……（技能点？）如果在一条路上放了x个技能点，这条路经过了y个货物，那么B公司就会收x*y的钱。现在要求的是，B公司最大获利和A公司在付费最大时的最小值，和这个问题完全倒过来。

首先有一个结论是B公司一定会把所有技能点一股脑全放在流量最大的那条边上。（贪心显然）注意是当前图上的流量而不是原图容量。那么这个问题就转化成了有上/下界限制的最大最小流。对于第一个问题，我们二分一个流的上界，首先判断这个其实就相当于一个正常的网络流，直接跑dinic即可，然后记录一下是否与一开始跑出来的值是相等的，这样二分求最大值即可。（答案就是当前容量上限的最大值*p）

而对于第二个问题，我们二分流的下界。这个时候就是一个有上下界的网络流，要建立辅助源汇点那一套跑流。不过具体的二分操作依然没变。注意的是，如果在二分过程中，当前的下届大于原来的上界，就直接返回0.最后我们求出最小的下界，然后用它乘以p来更新答案。

但是这题坑点很多的……首先是因为这题重构图很多，注意不能大量用memset。还有就是在head复制的时候不要复制少了，辅助源汇点编号不要小了（因为这题S，T）是给定的……，还有就是这次在判断最小流的时候……删除辅助源汇点最稳妥的做法是把其head设为-1，这样可以保证不会跑到。（不知道为啥，这次如果像以前一样把源汇点直接连的边设为不可走会GG……）

看一下代码吧。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<set>

#include<vector>

#include<map>

#include<queue>

#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<int,int>

#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 <ll> 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;

}

巴特西

ZOJ3496 Assignment

最新文章

热门文章