1333. [ZJOI2009] 假期的宿舍
★★☆ 输入文件:zjoi09holiday.in 输出文件:
zjoi09holiday.out
简单对比
时间限制:1 s 内存限制:256 MB
看谁留校
S->需房间的-》有房间-》T
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<cstdlib>
#include<algorithm>
#define V 105
#define mod 1000000007
#define LL long long
using namespace std;
int n,m,sd,T,S;
int a[V][V],s[V],b[V],pre[V],dep[V],q[V];
struct da
{int to,next,dis;
}Edge[V*V*V];
int head[V*V],tot;
inline void add(int x,int y,int zz)
{Edge[tot].to=y;Edge[tot].dis=zz;Edge[tot].next=head[x];head[x]=tot++; Edge[tot].to=x;Edge[tot].dis=0;Edge[tot].next=head[y];head[y]=tot++;
}
bool Bfs() {memset(dep, 0, sizeof(dep));int hd,tl;hd = tl = 0;q[++ tl] = S, dep[S] = 1;while(hd<tl) {int op = q[++hd];for(int i = head[op] ; i != -1 ; i = Edge[i].next) {if(Edge[i].dis&&(!dep[Edge[i].to])) {dep[Edge[i].to] = dep[op]+1;q[++ tl] = Edge[i].to;if(Edge[i].to==T) return true;} }}return false;
}
int Dfs(int op, int fw) {if(op==T) return fw; int tmp =fw,k;for(int i = head[op] ; i != -1 ; i = Edge[i].next) {if(Edge[i].dis&&tmp&&dep[Edge[i].to]==dep[op]+1) {k = Dfs(Edge[i].to, min(Edge[i].dis, tmp));if(!k) {dep[Edge[i].to] = 0; continue; }Edge[i].dis-= k, Edge[i^1].dis+= k,tmp-= k;}}return fw-tmp;
}
int solve()
{int i,flow=0;while(Bfs()){flow+=Dfs(S,mod); }return flow;
}
void Init()
{tot=0;memset(head,-1,sizeof(head));memset(s,0,sizeof(s));
}
inline int haha()
{//freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);freopen("zjoi09holiday.in","r",stdin); freopen("zjoi09holiday.out","w",stdout);memset(head,-1,sizeof(head));cin>>m;for(int p=1;p<=m;p++){int ans=0;scanf("%d",&n);Init();T=2*n+1;for(int i=1;i<=n;i++){cin>>s[i]; if(!s[i]){add(0,i,1);//cout<<i<<" &&"<<endl;ans++; }elseadd(i+n,T,1);} for(int i=1;i<=n;i++){cin>>b[i]; if(b[i]!=0&&b[i]!=1){b[i]=0;} if(s[i]&&!b[i]){add(0,i,1);// cout<<i<<" &&"<<endl;//add(i,T,1);ans++;}} for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>a[i][j];//if(!s[j])a[i][j]=0;if((i==j&&s[i]==1&&b[i]==0)||a[i][j]){add(i,j+n,1);//cout<<j<<" !!"<<endl;}} if(solve()==ans)cout<<"^_^"<<endl;else cout<<"T_T"<<endl;//if(w==ans)//else }return 0;
}
int gg=haha();
int main()
{;}