不easy啊。最终能够补第二个题了。！
顺便说一句：模版写残了就不要怪出题人啊 ~ （这残废模版研究了好长时间才找出错）
题目大意：
有一个n*m的矩阵。每个格子里都将有一个数。给你每一行数字之和和每一列数字之和。
求每个位置能填0~k之间的哪个数。假设有多种可能输出“Not Unique”，假设没有解输出“Impossible”，假设一组解则将其输出。
解题思路：
最大流： 不可能的条件：是行之和和列之和不想等或者建图后的最大流与他们不想等。
多组的条件是：在最大流后的残流网络中有长度大于2的环（实际中最少大于3）。
以下是代码：
#include#include #include #include #include #include #include #include
(x) : (y) ) #define min( x, y ) ( ((x) < (y)) ? (x) : (y) ) using namespace std; const int maxn=1000+10; const int maxm=200000+10; struct node { int v,w,next; node(int v=0,int w=0,int next=0):v(v),w(w),next(next) {}; } edge[maxm<<1]; int head[maxn],d[maxn],nEdge,S,T; bool vis[maxn]; int n,m,K; void addedge(int from,int to,int cap) { edge[++nEdge]=node(to,cap,head[from]); head[from]=nEdge; edge[++nEdge]=node(from,0,head[to]); head[to]=nEdge; } int deep[maxn]; bool bfs() { memset(deep,-1,sizeof(deep)); queue<int>q; q.push(S);//源点 deep[S]=0; while(!q.empty()) { int u=q.front(); q.pop(); int p=head[u]; while(p!=-1) { int v=edge[p].v; if(deep[v]==-1&&edge[p].w>0) { q.push(v); deep[v]=deep[u]+1; } p=edge[p].next; } } return deep[T]!=-1; //汇点 } int DFS(int src ,int flow) { if(src==T||flow==0)return flow; int sum=0,temp; int p=head[src]; while(p!=-1) { int v=edge[p].v; if(deep[v]==deep[src]+1&&edge[p].w>0) { temp=DFS(v,min(flow-sum,edge[p].w)); edge[p].w-=temp; edge[p^1].w+=temp; sum+=temp; if(flow-sum==0) return sum; } p=edge[p].next; } deep[src]=-1; return sum; } bool dfs(int u,int fa) { for(int k=head[u]; k!=-1; k=edge[k].next) { if(k==(fa^1)) continue; if(edge[k].w) { if(vis[edge[k].v]) return true; vis[edge[k].v]=true; if(dfs(edge[k].v,k)) return true; vis[edge[k].v]=false; } } return false; } int mat[404][404]; void ptmat() { printf("Unique\n"); memset(mat,0,sizeof(mat)); for(int u=1; u<=n; ++u) { for(int k=head[u]; k!=-1; k=edge[k].next) { int v=edge[k].v; if(v>n&&v<=n+m) mat[u][v-n]=K-edge[k].w; } } for(int i=1; i<=n; ++i) { for(int j=1; j<=m; ++j) { if(j>1) printf(" "); printf("%d",mat[i][j]); } printf("\n"); } } int main() { while(scanf("%d%d%d",&n,&m,&K)!=EOF) { memset(head,-1,sizeof(head)); nEdge=-1; S=0,T=n+m+1; int sum1=0,sum2=0,w; for(int i=1; i<=n; ++i) { scanf("%d",&w); sum1+=w; addedge(S,i,w); for(int j=1; j<=m; ++j) addedge(i,j+n,K); } for(int i=1; i<=m; ++i) { scanf("%d",&w); sum2+=w; addedge(i+n,T,w); } if(sum1!=sum2) printf("Impossible\n"); else { int flow=0; while(bfs())flow+=DFS(S,inf); if(flow!=sum1) printf("Impossible\n"); else { memset(vis,0,sizeof(vis)); bool flag=false; for(int i=1; i<=n; ++i) { if(dfs(i,-1)) { flag=true; break; } } if(flag) printf("Not Unique\n"); else ptmat(); } } } return 0; }