[二分+有上下界最大流] ZOJ3496: Assignment
题意
Company A wants to transport as many goods as possible from city S to city T. So they ask company B to do the transportation. There are n cities here in the problem and there are directed roads from cities i to city j with capacity cij.
【[二分+有上下界最大流] ZOJ3496: Assignment】After a long negotiation, A and B reach a consensus that A first decide how to transport the goods (Of course under the condition that most goods are transported and that the quantity transported in each road cannot exceed the capacity) and then B can assign non-negative integer unit transportation costs to each road such that the total unit transportation costs in all roads sum to P. So the money A has to pay is the sum of costs of all roads while the cost of a certain road is the quantity transported (assigned by A) multiplied by the unit transportation cost (assigned by B). Notice that since the goods are not divisible, the quantity transported for each road should be a non-negative integer.
Of course A wants to minimize the cost and B want to maximize the cost. So you are to work out what the total cost will be?
To make the problem more fun, you should also work out the total cost that A wants to maximize the cost while B wants to minimize it and other conditions keep the same.
2 ≤ n ≤ 500, 0 ≤ m ≤ 10000, 0 ≤ S, T < n, 0 ≤ P ≤ 100000
题解
这题题目意思比较绕，看懂了就是大水题了。
实际上B公司设定边权时肯定是贪心的只在流量最大（小）的一条上加P，而A公司就是要使流量最大（小）的边的流量最小（大）。
所以二分答案，然后刷有上下界的最大流验证即可。
#include
#include
#include
#include
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc();
int res=0,ff=1;
while(!('0'<=ch&&ch<='9')){ if(ch=='-') ff=-1;
ch=gc();
}
while('0'<=ch&&ch<='9') res=(res<<3)+(res<<1)+ch-'0', ch=gc();
return res*ff;
}
const int maxn=605, maxe=40005;
int n,m,S,T,SS,TT,P,_test,ans,MaxFlow;
struct Edge{
int from,to,flow,cap;
Edge(int t1=0,int t2=0,int t3=0,int t4=0){ from=t1;
to=t2;
flow=t3;
cap=t4;
}
} Es[maxe];
struct data{ int x,y,z;
} a[maxe];
int fir[maxn],nxt[maxe],tot=1;
void add(int x,int y,int z){
Es[++tot]=Edge(x,y,0,z);
nxt[tot]=fir[x];
fir[x]=tot;
Es[++tot]=Edge(y,x,0,0);
nxt[tot]=fir[y];
fir[y]=tot;
}
queue< int > que;
int N,d[maxn],pos[maxn],tmp[maxn];
bool Bfs(int S,int T){
memset(d,63,sizeof(d));
int INF=d[0];
que.push(S);
d[S]=0;
while(!que.empty()){
int x=que.front();
que.pop();
for(int j=fir[x];
j;
j=nxt[j]) if(d[Es[j].to]==INF&&Es[j].cap>Es[j].flow){
d[Es[j].to]=d[x]+1;
que.push(Es[j].to);
}
}
return d[T]!=INF;
}
int find_Dfs(int x,int flow,int T){
if(x==T||flow==0) return flow;
int res=0,t;
for(int &j=pos[x];
j;
j=nxt[j]){
if(d[x]+1==d[Es[j].to]&&(t=find_Dfs(Es[j].to,min(flow,Es[j].cap-Es[j].flow),T))>0){
Es[j].flow+=t;
Es[j^1].flow-=t;
res+=t;
flow-=t;
if(flow==0) break;
}
}
return res;
}
int Dinic(int S,int T){
int res=0;
while(Bfs(S,T)){
for(int i=1;
i<=N;
i++) pos[i]=fir[i];
res+=find_Dfs(S,1e+9,T);
}
return res;
}
void getMaxFlow(){
memset(fir,0,sizeof fir);
tot=1;
for(int i=1;
i<=m;
i++) add(a[i].x,a[i].y,a[i].z);
N=n;
MaxFlow=Dinic(S,T);
}
void Del(int x){
for(int j=fir[x];
j;
j=nxt[j]) Es[j].flow=Es[j].cap=Es[j^1].flow=Es[j^1].cap=0;
}
bool check(int _L,int _R){
memset(fir,0,sizeof fir);
tot=1;
N=n;
SS=++N;
TT=++N;
memset(tmp,0,sizeof tmp);
for(int i=1;
i<=m;
i++){
int fL=_L, fR=min(_R,a[i].z);
if(fL>fR) continue;
add(a[i].x,a[i].y,fR-fL);
tmp[a[i].x]-=fL;
tmp[a[i].y]+=fL;
}
int blc=0;
for(int i=1;
i<=n;
i++){
if(tmp[i]>0) add(SS,i,tmp[i]), blc+=tmp[i];
else add(i,TT,-tmp[i]);
}
add(T,S,1e+9);
if(Dinic(SS,TT)>1;
if(check(0,mid)) R=mid-1, ans=mid;
else L=mid+1;
}
printf("%lld ",((long long)ans)*P);
L=0,R=1000000;
ans=0;
while(L<=R){
int mid=(L+R)>>1;
if(check(mid,1e+9)) L=mid+1, ans=mid;
else R=mid-1;
}
printf("%lld\n",((long long)ans)*P);
}
return 0;
} 推荐阅读
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 尽力
- 死结。
- Y房东的后半生14
- 《跨界歌手》:亲情永远比爱情更有泪点
- 时间老了
- 深入理解Go之generate
- 陇上秋二|陇上秋二 罗敷媚
- 午门传说
- 【译】20个更有效地使用谷歌搜索的技巧