hdu4888 最大流（构造矩阵）

题意：

      让你构造一个矩阵，满足每一行的和，和每一列的和都等于他给的，还要判断答案是否唯一，还有一点就是矩阵内所有的数字都是[0,k]范围的。

思路：

      这个题目看完就让我想起了hdu3338，那个题目做了好久啊！哎！对于构造矩阵还是很简单的，我们构造两个点起s点和终点e，建图如下：

s -> 所有行       流量是当前行和

所有行 -> 所有列  流量为k

所有列 -> e       流量为当前列和

这样矩阵就构造好了，如果输出答案就直接去残余网络里面找就行了，下面说一下怎么判断最大流是否唯一，其实这个我们可以通过残余网络来找，只要能在残余网络上找到环就行了，这个结论值存在于无环图中，这里说的无环图是指建图的时候的正向图是无环的，对于这个题目就是无环图，这个题目还有一个坑点，就是一开始我是从终点开始搜直接找环，没有从起点是因为起点已经满流，正向流量全是0，根本跑不懂，但是从终点跑各种超时，超时出翔了，无语了我又枚举所有终点所连接的点开始跑，还是超时，最后是枚举起点所连接的点

开始跑的，500ms AC，我有点蛋疼，理论上对于一个环而言从哪个位置跑都可以找到环，我估计是数据里面给的 "能得到唯一答案" 的数据过多，这样就让很多正向的流量变成0，或者是不至于走了好几层才变成0，哎!这个不科学啊！

#include<stdio.h>
#include<string.h>
#include<queue>#define N_node 810
#define N_edge 350000
#define INF 1000000000

using namespace std;typedef struct
{
int to ,next ,cost;
}STAR;typedef struct
{
int x ,t;
}DEP;STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,list1[N_node] ,tot;
int deep[N_node] ,map[405][405];void add(int a ,int b ,int c)
{
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
E[++tot].to = a;
E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot;
}int minn(int x ,int y)
{
return x < y ? x : y;
}bool bfs_deep(int s ,int t ,int n)
{
xin.x = s ,xin.t = 0;
queue<DEP>q; q.push(xin);
memset(deep ,255 ,sizeof(deep));
deep[s] = 0;
while(!q.empty())
{
tou = q.front();
q.pop();
for(int k = list[tou.x] ;k ;k = E[k].next)
{
xin.x = E[k].to;
xin.t = tou.t + 1;
if(deep[xin.x] == -1 && E[k].cost)
{
deep[xin.x] = xin.t;
q.push(xin);
}
}
}
for(int i = 0 ;i <= n ;i ++)
list1[i] = list[i];
return deep[t] != -1;
}int DFS(int s ,int t ,int flow)
{
if(s == t) return flow;
int nowflow = 0;
for(int k = list1[s] ;k ;k = E[k].next)
{
list1[s] = k;
int c = E[k].cost;
int to = E[k].to;
if(!c || deep[to] != deep[s] + 1) continue;
int tmp = DFS(to ,t ,minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(nowflow == flow) break;
}
if(!nowflow) deep[s] = 0;
return nowflow;
}int DINIC(int s ,int t ,int n)
{
int ans = 0;
while(bfs_deep(s ,t ,n))
{
ans += DFS(s ,t ,INF);
}
return ans;
}int mark_r;
int mark[N_node];
void DFS_R(int from ,int s)
{
for(int k = list[s] ;k && !mark_r ;k = E[k].next)
{
int to = E[k].to;
if(k == (from ^ 1) || !E[k].cost) continue;
if(mark[to]) mark_r = 1;
mark[to] = 1;
if(!mark_r) DFS_R(k ,to);
mark[to] = 0;
}
}int main ()
{
int n ,m ,i ,j ,k ,num;
int s1 ,s2;
while(~scanf("%d %d %d" ,&n ,&m ,&k))
{
memset(list ,0 ,sizeof(list)) ,tot = 1;
int mkk = 0;
for(s1 = 0 ,i = 1 ;i <= n ;i ++)
{
scanf("%d" ,&num);
add(0 ,i ,num);
if(k * m < num) mkk = 1;
s1 += num;
}
for(s2 = 0 ,i = 1 ;i <= m ;i ++)
{
scanf("%d" ,&num);
add(i + n ,n + m + 1 ,num);
if(k * n < num) mkk = 1;
s2 += num;
}
if(s1 != s2 || mkk)
{
puts("Impossible"); continue;
}
int mk = tot + 1;
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= m ;j ++)
add(i ,j + n ,k);
int sum = DINIC(0 ,n + m + 1 ,n + m + 1);
if(sum != s1)
{
puts("Impossible"); continue;
}
mark_r = 0;
memset(mark , 0 ,sizeof(mark));
mark[n+m+1] = 1;
for(i = 1 ;i <= n ;i ++)
{
DFS_R(0 ,i);
if(mark_r) break;
}
if(mark_r)
{
puts("Not Unique");continue;
}
puts("Unique");
int t = 0;
for(i = mk ;i <= tot ;i += 2)
{
printf("%d" ,k - E[i].cost);
if(++t % m == 0) puts("");
else printf(" ");
}
}
return 0;
}