首页 > 代码库 > hdu 4888 Redraw Beautiful Drawings
hdu 4888 Redraw Beautiful Drawings
题目是一个矩阵，每行每列的数字的和都有一个上限，问是否存在可行方案，并且可行方案是否唯一。
第一问比较简单，行列建图，s到每个行节点容量为该行上限，每个列节点连接到t，容量为该列的上限，求最大流，如果满流则有可行方案。第二问就是判断最大流是否唯一，就是在原图中找一个环（经过一条边后不能马上走反向边），环上的边cap-flow都大于0。如果有这个环，那么不唯一，否则唯一。因为流量为k的两个流量图的差别肯定是一个个的环，否则流量不相同，只要按照这个环进行流量的重新分配就可以找到另一个方案。
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;#define maxn 1000#define INF 10000000struct Edge{ int from, to, cap, flow;}edges[360000];int n, m, s, t, kk, cnt;vector<int> G[maxn]; // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号bool vis[maxn]; // BFS使用int d[maxn]; // 从起点到i的距离int cur[maxn]; // 当前弧指针int map[410][410];void AddEdge(int from, int to, int cap){ edges[cnt].from=from; edges[cnt].to=to; edges[cnt].cap=cap; edges[cnt].flow=0; G[from].push_back(cnt); cnt++; edges[cnt].from=to; edges[cnt].to=from; edges[cnt].cap=0; edges[cnt].flow=0; G[to].push_back(cnt); cnt++;}bool BFS(){ memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); vis[s] = 1; d[s] = 0; 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 flow = 0; while(BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow;}int dfs(int x,int fa){ int i; for(i=0;i<G[x].size();i++) { int v=edges[G[x][i]].to; int cap=edges[G[x][i]].cap; int flow=edges[G[x][i]].flow; if(v==fa) continue; if(v!=s&&v!=t&&cap-flow) { if(vis[v]) return 1; vis[v]=1; if(dfs(v,x)) return 1; vis[v]=0; } } return 0;}int main(){ while(scanf("%d%d%d",&n,&m,&kk)!=EOF) { int i,j,x; int flag=0; int sum1=0,sum2=0; s=0;t=n+m+1;cnt=0; for(i=0;i<=t;i++) G[i].clear(); for(i=1;i<=n;i++) {scanf("%d",&x); sum1+=x; AddEdge(s,i,x);} for(i=1;i<=m;i++) {scanf("%d",&x); sum2+=x; AddEdge(i+n,t,x);} if(sum1!=sum2) {printf("Impossible\n"); continue;} for(i=1;i<=n;i++) for(j=1;j<=m;j++) AddEdge(i,j+n,kk); if(Maxflow()!=sum1) {printf("Impossible\n"); continue;} memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) { vis[i]=1; if(dfs(i,-1)) { flag=1; break; } vis[i]=0; } if(flag==1) printf("Not Unique\n"); else { printf("Unique\n"); for(j=1;j<=n;j++) for(i=0;i<G[j].size();i++) { int v=edges[G[j][i]].to; if(v!=s) map[j][v-n]=edges[G[j][i]].flow; } for(i=1;i<=n;i++) { printf("%d",map[i][1]); for(j=2;j<=m;j++) printf(" %d",map[i][j]); printf("\n"); } } } return 0;}
hdu 4888 Redraw Beautiful Drawings
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。