首页 > 代码库 > NYIST 489 哭泣天使
NYIST 489 哭泣天使
哭泣天使
时间限制：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)
样例输入
2
2 3
1 1
1 1 0
3 3
0 1 2
3 0 0
样例输出
Not Sure
Terrible
来源
[张云聪]原创
上传者
张云聪
解题：最大流，居然卡dinic，把源点汇点反转，建立逆图，果断AC了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 810;18 struct arc {19 int to,flow,next;20 arc(int x = 0,int y = 0,int z = -1) {21 to = x;22 flow = y;23 next = z;24 }25 };26 arc e[maxn*maxn];27 int head[maxn],d[maxn],cur[maxn];28 int tot,n,m,S,T;29 void add(int u,int v,int flow) {30 e[tot] = arc(v,flow,head[u]);31 head[u] = tot++;32 e[tot] = arc(u,0,head[v]);33 head[v] = tot++;34 }35 bool bfs() {36 queue<int>q;37 memset(d,-1,sizeof(d));38 d[T] = 1;39 q.push(T);40 while(!q.empty()) {41 int u = q.front();42 q.pop();43 for(int i = head[u]; ~i; i = e[i].next) {44 if(e[i].flow && d[e[i].to] == -1) {45 d[e[i].to] = d[u] + 1;46 q.push(e[i].to);47 }48 }49 }50 return d[S] > -1;51 }52 int dfs(int u,int low) {53 if(u == S) return low;54 int tmp = 0,a;55 for(int &i = cur[u]; ~i; i = e[i].next) {56 if(e[i].flow > 0 && d[e[i].to] == d[u] + 1&&(a=dfs(e[i].to,min(low,e[i].flow)))) {57 e[i].flow -= a;58 e[i^1].flow += a;59 tmp += a;60 low -= a;61 if(!low) break;62 }63 }64 if(!tmp) d[u] = -1;65 return tmp;66 }67 int dinic(int sum) {68 int ans = 0;69 while(bfs()) {70 memcpy(cur,head,sizeof(head));71 ans += dfs(T,INF);72 if(ans > sum) break;73 }74 return ans;75 }76 int main() {77 int tmp,sum,t,sum2;78 scanf("%d",&t);79 while(t--) {80 scanf("%d %d",&n,&m);81 memset(head,-1,sizeof(head));82 sum2 = sum = S = tot = 0;83 T = n+m+1;84 for(int i = 1; i <= n; i++){85 scanf("%d",&tmp);86 add(i,S,tmp);87 sum += tmp;88 for(int j = n+1; j <= n+m; ++j) add(j,i,1);89 }90 for(int i = 1; i <= m; ++i){91 scanf("%d",&tmp);92 add(T,n+i,tmp);93 sum2 += tmp;94 }95 printf("%s\n",sum == sum2&&dinic(sum) == sum?"Not Sure":"Terrible");96 }97 return 0;98 }
NYIST 489 哭泣天使