【bzoj3698】XWW的难题 有上下界的网络流

源点S向每一行连一条容量为(a[i][n],a[i][n]+1)的边
每一列向汇点T连一条容量为(a[n][i],a[n][i]+1)的边
行i向列j连一条容量为(a[i][j],a[i][j]+1)的边

求最大流

#include
#include
#include
#include
#include
#include
#define maxn 210
#define maxm 100010
#define inf 1000000000using namespace std;int head[maxn],to[maxm],c[maxm],next[maxm],q[maxn],d[maxn],in[maxn],cnt[maxn];
double a[maxn][maxn];
int n,m,num,s,t,S,T,ans;void addedge(int x,int y,int z)
{num++;to[num]=y;c[num]=z;next[num]=head[x];head[x]=num;num++;to[num]=x;c[num]=0;next[num]=head[y];head[y]=num;
}bool bfs()
{memset(d,-1,sizeof(d));int l=0,r=1;q[1]=S;d[S]=0;while (l0) cnt[i]=num+1,addedge(S,i,in[i]);else if (in[i]<0) cnt[i]=num+1,addedge(i,T,-in[i]);Dinic();for (int i=s;i<=t;i++)if (cnt[i] && c[cnt[i]]) return 0;return 1;
}int main()
{scanf("%d",&n);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)scanf("%lf",&a[i][j]);int l=0,r=inf,ans=-1;while (l<=r){int mid=(l+r)/2;if (check(mid)) ans=mid,l=mid+1; else r=mid-1;}if (ans==-1) printf("No\n");else printf("%d\n",ans*3);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！