神奇的上下界网络流----- （总结by ： becauseofyou）(三)
;
if(in[i] > 0) add_edge(ss,i,in[i],0);
if(in[i] < 0) add_edge(i,tt,-in[i],0);
}
SAP(ss,tt,tt+1);
for(i=head[ss];i!=-1;i=edge[i].next)
{
if(edge[i].c) return false;
}
for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
int id = ID(i,j);
for(k = head[id]; k!=-1; k=edge[k].next)
{
if(edge[k].v <= 2*n*m)
{
ans[i][j] = low[i][j] + edge[k^1].c;
}
}
}
}
for(i = 1; i <= m; i++)
{
printf("%d",ans[i][1]);
for(j = 2; j <= n; j++)
{
printf(" %d",ans[i][j]);
}
puts("");
}
/* if(check()) {
puts("YES");
} else puts("NO");*/
return true;
}
int main()
{
int t;
// freopen("budget.in","r",stdin);
// freopen("budget.out","w",stdout);
scanf("%d",&t);
for(int i = 0; i < t; i++)
{
if(i) puts("");
if(!init())
{
puts("IMPOSSIBLE");
}
else
{
if(!solve()) puts("IMPOSSIBLE");
}
}
return 0;
}
zoj 那题很好想，需要两次二分，但不是太好写，附上代码吧。
[cpp]
http://acm.zju.edu.cn/onlinejudge/showProblem.do problemCode=3496
#include
#include
typedef long long lld;
const int MAX=510;
const int INF=100000000;
struct EDGE
{
int v,c,next;
}edge[1000000];
int E,head[MAX];
int gap[MAX],cur[MAX];
int pre[MAX],dis[MAX];
void add_edge(int s,int t,int c,int cc)
{
edge[E].v=t; edge[E].c=c;
edge[E].next=head[s];
head[s]=E++;
edge[E].v=s; edge[E].c=cc;
edge[E].next=head[t];
head[t]=E++;
}
int min(int a,int b){return (a==-1||b
int SAP(int s,int t,int n)
{
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
int i;
for(i=0;i
int u=pre[s]=s,aug=-1,v;
int maxflow = 0;
gap[0]=n;
while(dis[s]
{
loop: for(i=cur[u];i!=-1;i=edge[i].next)
{
v=edge[i].v;
if(edge[i].c>0&&dis[u]==dis[v]+1)
{
aug=min(aug,edge[i].c);
pre[v]=u;
cur[u]=i;
u=v;
if(u==t)
{
for(u=pre[u];v!=s;v=u,u=pre[u])
{
edge[cur[u]].c-=aug;
edge[cur[u]^1].c+=aug;
}
maxflow+=aug;
aug=-1;
}
goto loop;
}
}
int mindis=n;
for(i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].v;
if(edge[i].c>0&&dis[v]
{
cur[u]=i;
mindis=dis[v];
}
}
if((--gap[dis[u]])==0)break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return maxflow;
}
int n , m , S , T , P , ans1 , ans2 , maxc , minc;
int max_flow;
int u[10010] , v[10010] , c[10010];
int in[510];
void init()
{
E = 0;
memset(head,-1,sizeof(head[0])*600);
}
void Map_Init(int mid) // 流量上界为mid ，每条边的上界就是mid与c的最小值
{
init();
for(int i = 0; i < m; i++)
{
add_edge(u[i],v[i],min(mid,c[i]),0);
}
}
void question1() // 二分上界
{
int l = 0 , r = maxc