首页 > 代码库 > hdu 4888
hdu 4888
网络流建模,建模不难,难在找环;
#include<cstdio>#include<algorithm>#include<vector>#include<queue>#include<cstring>#define inf 1<<30#define maxn 2100using namespace std;struct edge{ int from,to,cap,flow; edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow) {}};struct dinic{ int n,m,s,t; vector<edge>edges; vector<int>g[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; bool ishuan[maxn]; int jie[550][550]; void init(int n) { this->n=n; for(int i=0; i<n; i++) g[i].clear(); edges.clear(); memset(d,0,sizeof d); memset(cur,0,sizeof cur); } void addedge(int from,int to,int cap) { edges.push_back(edge(from,to,cap,0)); edges.push_back(edge(to,from,0,0)); m=edges.size(); g[from].push_back(m-2); g[to].push_back(m-1); }queue<int >q; bool bfs() { memset(vis,0,sizeof vis); while(!q.empty()) q.pop(); q.push(s); d[s]=0; vis[s]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0; i<g[x].size(); i++) { edge& e=edges[g[x][i]]; if(!vis[e.to]&&e.cap>e.flow) { vis[e.to]=1; d[e.to]=d[x]+1; q.push(e.to); } } } return vis[t]; } int dfs(int x,int a) { if(x==t||a==0)return a; int flow=0,f; for(int &i=cur[x]; i<g[x].size(); i++) { edge& e=edges[g[x][i]]; if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0) { e.flow+=f; edges[g[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0)break; } } return flow; } int maxflow(int s,int t) { this->s=s; this->t=t; int flow=0; while(bfs()) { memset(cur,0,sizeof cur); flow+=dfs(s,inf); } return flow; } bool panhuan(int v,int f) { if(ishuan[v])return 1; ishuan[v]=1; for(int i=0;i<g[v].size();i++) { if(g[v][i]==(f^1))continue; int tmp=g[v][i]; if(edges[tmp].to==t||edges[tmp].to==s)continue; if(edges[tmp].cap-edges[tmp].flow>0) { if(panhuan(edges[tmp].to,tmp))return 1; } } ishuan[v]=0; return 0; } bool haofang(int x) { memset(ishuan,0,sizeof ishuan); for(int i=1; i<=x; i++) { if(panhuan(i,-1))return 1; } return 0; } void getans(int x,int y) { for(int i=0;i<edges.size();i++) { if(edges[i].cap&&edges[i].from>0&&edges[i].from<=x) { jie[edges[i].from][edges[i].to-x]=edges[i].flow; } } }};int hang[550];int lie[550];dinic solve;int main(){ int n,m,k; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { int sum_hang=0,sum_lie=0; for(int i=1; i<=n; i++) { scanf("%d",&hang[i]); sum_hang+=hang[i]; } for(int i=1; i<=m; i++) { scanf("%d",&lie[i]); sum_lie+=lie[i]; } if(sum_hang!=sum_lie) { puts("Impossible"); continue; } solve.init(n+m+2); solve.s=0; solve.t=n+m+1; for(int i=1;i<=n;i++) { solve.addedge(solve.s,i,hang[i]); for(int j=1;j<=m;j++) solve.addedge(i,j+n,k); } for(int i=1;i<=m;i++) solve.addedge(i+n,solve.t,lie[i]); int ans=solve.maxflow(solve.s,solve.t); if(ans!=sum_hang) puts("Impossible"); else { if(solve.haofang(n)) puts("Not Unique"); else { puts("Unique"); solve.getans(n,m); for(int i=1;i<=n;i++) { for(int j=1;j<m;j++) printf("%d ",solve.jie[i][j]); printf("%d\n",solve.jie[i][m]); } } } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。