题目
input
output
Sample Input 1 3 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 Sample Output ˆ_ˆ HINT 对于30% 的数据满足1 ≤ n ≤ 12。 对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。
思路： 人与座位有着一一对应的关系，自然想到二分图匹配，题目求是否存在方案，那就是问能不能把要求的人都匹配到床上去，可以选择的就连边，用匈牙利算法即可，如果匹配数等于人的数量，那么完美匹配。
当然这道题也可以用网络流跑，应该会快一点。
如果不太懂匈牙利算法的话点这里
#include<cstdio> #include<cstring> using namespace std; const int N = 101000; struct Edge{ int to, next; }ed[N*2]; int head[N], vis[N], link[N], idc, tot; bool in[N], out[N]; void adde(int u, int v){ ed[++idc].to = v; ed[idc].next = head[u]; head[u] = idc; } bool find(int u){ if(u == 0) return true; for(int i = head[u]; i; i = ed[i].next){ int v = ed[i].to; if( !vis[v] ){ vis[v] = 1; if( !link[v] || find(link[v]) ){//找到匹配，更换匹配 link[v] = u; link[u] = v; return true; } } } return false; } int main(){ freopen("class.in", "r", stdin); freopen("class.out", "w", stdout); int T; scanf("%d", &T); while ( T-- ){ memset(head, 0, sizeof(head)); memset(vis, 0, sizeof(vis)); memset(link, 0, sizeof(link)); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); memset(ed, 0, sizeof(ed)); int n; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &in[i]); for(int i=1; i<=n; i++) scanf("%d", &out[i]); tot = n; for(int i=1; i<=n; i++){ int cc; if( in[i] && out[i] == 1 ) { tot--; for(int x=1; x<=n; x++) scanf("%d", &cc); continue; } for(int j=1; j<=n; j++){ scanf("%d", &cc); if(cc && in[j]) adde(i, j+n); if( i == j && in[i]) adde(i, j+n); } } int ans = 0; for(int i=1; i<=n+n; i++){ memset(vis,0,sizeof(vis)); if( !link[i] ) if( find(i) ) ans++;//每次多一个匹配 } if(ans == tot) printf("^_^\n"); else printf("T_T\n"); //printf("%d %d\n", ans, tot); } return 0; }