链接：click here
题意描述：
哭泣天使
时间限制：1000 ms | 内存限制：65535 KB
难度：5
描述
Doctor Who乘着Tardis带着Amy来到了一个星球，一开Tadis大门，发现这个星球上有个壮观的石像群，全是一些天使石像，有的石像在哭泣，有的石像像在微笑，共有m行n列，Doctor用“音速起子”扫描了一下整个石像群，得到了每行天使中在哭泣的天使的个数。当他与Amy在这里行走了一段时间之后，Doctor忽然想起了什么，怀疑这些石像是不是传说中的一种黑暗生物——“哭泣天使”——一种看似石像，却会在人不看它的时候移动，会强制把人送回某个过去的时间点，并借此汲取时间能量的生物。Doctor可不想自己和Amy迷失在一个未知的时间点里，于是Doctor立刻用“音速起子”又扫描了整个石像群，想再看看每行的在哭泣的天使个数与刚才是否相符，但是，越急就越容易出错，他一不小心扫描错了，，扫描出了每列中哭泣的天使的个数。现在，由于音速起子的能量不足了，他不能够再次扫描，他想根据已有的数据判断出是否有天使改变了自己的表情，从哭泣变成不哭泣或者从不哭泣变成哭泣了。
输入第一行是一个整数T，表示共有T组测试数据(T<=50)每组测试数据第一行是两个整数m,n(0<m,n<=300)分别表示行数和列数随后的两行分别有m个数和n个数分别表示对应m行中哭泣的天使石像的个数与对应n个列中哭泣的天使石像的个数。输出如果能根据已有信息判断出必然有石像改变了表情，则输出Terrible如果根据已有信息无法确定石像发生了改变，则输出Not Sure (有时，你确定两次扫描时状态相同，但由于不确定之间是否发生过改变，故也输出Not Sure)样例输入22 31 11 1 03 30 1 23 0 0样例输出Not SureTerrible花了一天时间，最后终于弄懂是到最大流。
思路：该题主要在于 1建边。 2 建超级源点和超级汇点。因为一行和一列单独确定一个点，所以把所有的行和列当成点建边，容量为1，再建一个源点s，与所有的行相连，容量为每一行哭泣天使的数量，建立一个汇点t，与所有的列相连，容量为相应列哭泣天使的容量，然后求最大流，与之前得到行的数量比较之。另外，如果输入的数据行和列的和都不一样，那么不需要判断，必然有天使改变状态，直接输出Terrible，否则输出Not Sure。
代码（Dinic实现）：
#include <math.h>#include <queue>#include <deque>#include <vector>#include <stack>#include <stdio.h>#include <ctype.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <algorithm>using namespace std;#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};const double eps = 1e-6;const double Pi = acos(-1.0);static const int INF = ~0U >> 2;//比0x3f3f3f3f还大static const int MAXN = 600 + 5;struct Edge{int from,to,cap,flow;Edge(int f,int t,int c,int ff):from(f),to(t),cap(c),flow(ff) {};};vector<Edge> edges;vector<int> G[MAXN];int N,M,S,T,i,j;int iter[MAXN],level[MAXN];bool vis[MAXN];void Init(){S = 0;T = N+M+1;for(int i = 0; i <= T; ++i)G[i].clear();edges.clear();}bool add_edge(int from,int to,int cap){edges.push_back(Edge(from,to,cap,0));edges.push_back(Edge(to,from,0,0));int sz = edges.size();G[from].push_back(sz-2);G[to].push_back(sz-1);}bool BFS(){memset(vis,false,sizeof(vis));level[S] = 0;vis[S] = true;queue<int> Q;Q.push(S);while(!Q.empty()){int u = Q.front();Q.pop();for(int i = 0; i < (int)G[u].size(); ++i){Edge& e = edges[G[u][i]];if(!vis[e.to]&&e.cap > e.flow){vis[e.to] = true;level[e.to] = level[u] + 1;Q.push(e.to);}}}return vis[T];}int DFS(int u,int a){if(u==T||a==0)return a;int f,flow = 0;for(int& i = iter[u]; i < (int)G[u].size(); ++i){Edge& e = edges[G[u][i]];if(level[e.to]==level[u]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){e.flow += f;edges[G[u][i]^1].flow -= f;flow += f;a -= f;if(a==0)break;}}return flow;}int Dinic(){int flow = 0;while(BFS()){memset(iter,0,sizeof(iter));flow += DFS(S,INF);}return flow;}bool Solve()//关键{int c,sum1= 0,sum2 = 0;scanf("%d%d",&N,&M);Init();for(int i = 1; i <= N; ++i){scanf("%d",&c);sum1+= c;add_edge(S,i,c);}for(int i = 1; i <= M; ++i){scanf("%d",&c);sum2+= c;add_edge(i+N,T,c);}if(sum1!= sum2)return true;for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)add_edge(i,j+N,1);int flow = Dinic();if(flow == sum1)return false;return true;}int main(){int T;scanf("%d",&T);while(T–){if(Solve())puts("Terrible");elseputs("Not Sure");}return 0;//printf("%d %d\n",0x3f3f3f3f,~0U >> 2);}
人情似纸张张薄，世事如棋局局新。
