1433: [ZJOI2009]假期的宿舍
Time Limit: 10 Sec
Memory Limit: 162 MB
[
Submit][
Status][
Discuss]
Description
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。
Source
考这么水的题，愣是被我数组开小RE了8个点
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define INF 0x7fffffff
using namespace std;
const int N = 205;
int last[N],S,T,n,h[N],q[N],cnt=1,cur[N],sign[N],ans,MT,inclass[N];
struct Edge{
int to,next,v;
}e[N*40];
void insert( int u, int v, int w ){
e[++cnt].to = v; e[cnt].next = last[u]; e[cnt].v = w; last[u] = cnt;
e[++cnt].to = u; e[cnt].next = last[v]; e[cnt].v = 0; last[v] = cnt;
}
bool bfs(){
memset(h,-1,sizeof(h));
int tail = 1, head = 0;
q[0] = 0; h[0] = 0;
while( tail != head ){
int now = q[head++];
for( int i = last[now]; i; i = e[i].next )
if( h[e[i].to] == -1 && e[i].v ){
h[e[i].to] = h[now] + 1;
q[tail++] = e[i].to;
}
}
return h[T] != -1;
}
int dfs( int x, int f ){
int w,used=0;
if( x == T ) return f;
for( int i = cur[x]; i; i = e[i].next )
if( h[e[i].to] == h[x] + 1 ){
w = dfs(e[i].to,min(e[i].v,f-used));
e[i].v -= w; e[i^1].v += w; used += w;
if( e[i].v ) cur[x] = i; if( f == used ) return f;
}
if( !used ) h[x] = -1;
return used;
}
void dinic(){
while( bfs() ){
for( int i = S; i <= T; i++ ) cur[i] = last[i];
ans += dfs(S,INF);
}
}
int main(){
scanf("%d", &MT);
while( MT-- ){
scanf("%d", &n); S = 0; T = n*2+1; int yu = n; ans = 0;
cnt = 1; memset(last,0,sizeof(last)); memset(sign,0,sizeof(sign));
for( int i = 1; i <= n; i++ ) scanf("%d", &inclass[i]);
for( int i = 1,x; i <= n; i++ ){ scanf("%d", &x); if( inclass[i] && x == 1 ) sign[i] = 1; }
for( int i = 1; i <= n; i++ ) if( !sign[i] ) insert(S,i,1);
for( int i = 1; i <= n; i++ ) if( inclass[i] ) insert(i+n,T,1);
for( int i = 1; i <= n; i++ )
for( int j = 1,x; j <= n; j++ ){
scanf("%d", &x);
if( sign[i] || !inclass[j] ) continue;
if( x || i == j ) insert(i,j+n,1);
}
for( int i = 1; i <= n; i++ ) if( sign[i] ) yu--;
dinic();
if( ans == yu ) puts("^_^");
else puts("T_T");
}
return 0;
}
