nyoj 489
哭泣天使
時間限制：1000?ms ?|? 內存限制：65535?KB 難度：5 描述Doctor Who乘著Tardis帶著Amy來到了一個星球，一開Tadis大門，發現這個星球上有個壯觀的石像群，全是一些天使石像，有的石像在哭泣，有的石像像在微笑，共有m行n列，Doctor用“音速起子”掃描了一下整個石像群，得到了每行天使中在哭泣的天使的個數。當他與Amy在這里行走了一段時間之后，Doctor忽然想起了什么，懷疑這些石像是不是傳說中的一種黑暗生物——“哭泣天使”——一種看似石像，卻會在人不看它的時候移動，會強制把人送回某個過去的時間點，并借此汲取時間能量的生物。Doctor可不想自己和Amy迷失在一個未知的時間點里，于是Doctor立刻用“音速起子”又掃描了整個石像群，想再看看每行的在哭泣的天使個數與剛才是否相符，但是，越急就越容易出錯，他一不小心掃描錯了，掃描出了每列中哭泣的天使的個數。現在，由于音速起子的能量不足了，他不能夠再次掃描，他想根據已有的數據判斷出是否有天使改變了自己的表情，從哭泣變成不哭泣或者從不哭泣變成哭泣了。
輸入每組測試數據第一行是兩個整數m,n(0<m,n<=300)分別表示行數和列數
隨后的兩行分別有m個數和n個數分別表示對應m行中哭泣的天使石像的個數與對應n個列中哭泣的天使石像的個數。
如果根據已有信息無法確定石像發生了改變，則輸出Not Sure (有時，你確定兩次掃描時狀態相同，但由于不確定之間是否發生過改變，故也輸出Not Sure)
Terrible
解題思路：這道題我最開始的想法就是貪心，以每一列為基準，用每一行的哭泣天使數去滿足這一列的哭泣天數。。可是WA啦。。。
查了下別人的思路，確實很難想到是網絡流，因為一行和一列單獨確定一個點，所以把所有的行和列當成點建邊，容量為1，再建一個源點s，與所有的行相連，容量為每一行哭泣天使的數量，建立一個匯點t，與所有的列相連，容量為相應列哭泣天使的容量，然后求最大流，與之前得到行的數量比較之。另外，如果輸入的數據行和列的和都不一樣，那么不需要判斷，必然有天使改變狀態，直接輸出Terrible，否則輸出Not Sure。
圖論的算法都是非常靈活的，很多問題看似和圖沒有關系，都能夠最終轉化到圖論上。。關鍵還是在于建圖，只能不斷總結，多做題。
AC:
#include<stdio.h> #include<string.h> #include <iostream> using namespace std; #define INF 1<<29; int s,t; //s:源點 t:匯點 int m; //頂點數 int cf[605][605]; //殘留容量 int flow; //當前最大流 int cf_path; //本次可增廣的流量（本次增廣路徑的殘留容量） bool flag; //本次增廣路徑是否找到 int vh[1000]; //各高度的頂點個數 int h[1000]; //各頂點的高度，又稱為“距離標號”——到匯點距離的下界（邊權值都為1） void sap() {flow =cf_path=s=t=0;flag=false;memset(cf,0,sizeof(cf));memset(vh,0,sizeof(vh));memset(h,0,sizeof(h)); } void find_path_sap(int cur) {if(cur==t){flow++;flag=true;return;}int i;int minH=m*2;int tmp_cf_path=cf_path;for(i=0;i<=m;i++){if(cf[cur][i]){if(h[i]+1==h[cur]){find_path_sap(i);if(h[1]>=m) return;if(flag) break;//此句不加會錯、、、}if(h[i]<minH) minH=h[i];}}if(flag){cf[cur][i]--;cf[i][cur]++;}else{vh[h[cur]]--;if(vh[h[cur]]==0) h[0]=m;h[cur]=minH+1;vh[h[cur]]++;} } int solve() {vh[0]=m;flow=0;while(h[0]<m)//h[1]保持<m，一旦增長到m，就不再存在任何增廣路徑{flag=false;cf_path=INF;find_path_sap(s);}return flow; } void addEdge(int x,int y,int c) {cf[x][y]+=c; } int main() {int mm,a;scanf("%d",&a);while(a--){int cn,n;scanf("%d%d",&cn,&n);sap();mm=cn+n+3;s=0;t=mm;m=mm;int i,cf=0,kf=0;for(i=1;i<=cn;i++){int c;scanf("%d",&c);cf+=c;addEdge(0,i,c);for(int j=cn+1;j<=cn+n;j++)addEdge(i,j,1);}for(i=cn+1;i<=cn+n;i++){int x;scanf("%d",&x);kf+=x;addEdge(i,cn+n+3,x);}if(cf!=kf)printf("Terrible\n");else{int hs;hs=solve();if(cf==hs)printf("Not Sure\n");else printf("Terrible\n");}}return 0; }
總結
- 上一篇： extundelete反删除总结
- 下一篇： 前端工作流程自动化——Grunt/Gul