ZOJ|【二分+上下界最大流】ZOJ3496 Assignment
题面在这里
首先要明确，B公司肯定会把流量最大（小）的边代价设为P，其他代价为0（根据贪心原理）。
然后就是要使 流量最大的边最小（或流量最小的边最大）
二分枚举答案，然后就确定了每条边的流量范围
妥妥的上下界最大流
注意：如果二分确定的范围不在一条边原有的流量范围内，就验证失败
（因为流量取不到当前的值）
这个错误很容易被忽略，我因此WA了一个下午……
【ZOJ|【二分+上下界最大流】ZOJ3496 Assignment】示例程序：
#include
#include
#include
#define LL long long
#define del_e(x) flw[x]=cap[x]=flw[x^1]=cap[x^1]=0
using namespace std;
const int maxn=605,maxe=40005,INF=0x3f3f3f3f;
int tst,n,e,S,T,P,maxflow;
int tot,son[maxe],nxt[maxe],lnk[maxn],cap[maxe],flw[maxe];
#define nc getchar
inline int red(){
int res=0,f=1;
char ch=nc();
while (ch<'0'||'9'0){
flw[j]+=f;
flw[j^1]-=f;
flow-=f;
res+=f;
if (flow==0) break;
}
return res;
}
int Dinic(int S,int T){
int res=0;
while (bfs(S,T)){
memcpy(pos,lnk,sizeof(lnk));
res+=dfs(S,INF,T);
}
return res;
}
int tmp[maxn];
inline void Del(int x){
for (int j=lnk[x];
j;
j=nxt[j]) del_e(j);
}
bool check(int L,int R){
tot=1;
memset(lnk,0,sizeof(lnk));
memset(tmp,0,sizeof(tmp));
int SS=n+1,TT=n+2;
for (int i=1;
i<=e;
i++){
int l=L,r=min(R,a[i].z);
if (l>r) return 0;
tmp[a[i].x]-=l;
tmp[a[i].y]+=l;
add(a[i].x,a[i].y,r-l);
}
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,INF);
if (Dinic(SS,TT)>1;
if (check(0,mid)) R=mid-1,ans=mid;
else L=mid+1;
}
printf("%lld ",(LL)ans*P);
L=0,R=100000,ans=0;
while (L<=R){
int mid=L+R>>1;
if (check(mid,INF)) L=mid+1,ans=mid;
else R=mid-1;
}
printf("%lld\n",(LL)ans*P);
}
return 0;
} 推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长