bzoj1433 假期的宿舍 [最大流]

in 题目 with 0 comment

Description

des.jpg


Input

inp.jpg


Output

oup.jpg


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 $


Solution

这道题应该属于无源无汇最大流问题,我们选0为S,101为T,与S相连的点为$(1,2,\dots ,n)$,如果需要床则连边;与T相连的点为$(n+1,n+2,\dots ,2*n)$,如果有床位则连边;中间如果i与j认识,则连$i\rightarrow j$ , 这样见图后跑一边dinic找出最大流,判断是否与所需床位相等即可


Code

#include<bits/stdc++.h>
#define maxn 110
#define maxe 30001
#define INF 0x7f7f7f7f
//#define DEBUG
using namespace std;
const int S=0,T=101;
int n,tot,cnt,ans;
int head[maxn],dis[maxn];
bool sc[maxn];

struct edge
{
    int to,next,v;
}E[maxe];

inline int read()
{
    char ch;
    int read=0,sign=1;
    do
        ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-');
    if(ch=='-') sign=-1,ch=getchar();
    while(ch>='0' && ch<='9')
    {
        read=read*10+ch-'0';
        ch=getchar();
    }
    return sign*read;
}

inline void ins(int u,int v,int w) 
{ ++cnt;E[cnt].to=v;E[cnt].v=w;E[cnt].next=head[u];head[u]=cnt; }

inline void insert(int u,int v,int w) 
{ ins(u,v,w),ins(v,u,0); }

bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    q.push(0);
    dis[0]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        int v=head[now];
        while(v)
        {
            if(E[v].v&&dis[E[v].to]==-1)
            {
                dis[E[v].to]=dis[now]+1;
                q.push(E[v].to);
            }
            v=E[v].next;
        }
    }
    if(dis[T]==-1) return 0;
    else return 1;
}

int dfs(int x,int flow)
{
    if(x==T) return flow;
    int v=head[x],used=0,w;
    while(v)
    {
        if(E[v].v&&dis[E[v].to]==dis[x]+1)
        {
            w=flow-used;
            w=dfs(E[v].to,min(E[v].v,w));
            E[v].v-=w;
            E[v^1].v+=w;
            used+=w;
            if(used==flow) return flow;
        }
        v=E[v].next;
    }
    if(!used) dis[x]=-1;
    return used;
}

void dinic() { while(bfs()) ans+=dfs(0,INF); }//cerr<<"ans="<<ans<<" "; }

int main()
{
    int num=read();
    while(num--)
    {
        tot=ans=0,cnt=1;
        memset(head,0,sizeof(head));
        n=read();
        for(int i=1;i<=n;++i)
        {
            sc[i]=read();
            if(sc[i]) insert(i+n,T,1);
        }
        for(int i=1;i<=n;++i)
        {
            int x=read();
            if(!sc[i]||(sc[i]&&!x)) insert(S,i,1),tot++;
        } 
        //cerr<<"tot="<<tot<<endl;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
            {
                int x=read();
                if(x||i==j) insert(i,j+n,1);
            }
    #ifdef DEBUG
        for(int i=1;i<=cnt;++i) 
            printf("%d->to=%d,next=%d,v=%d\n",i,E[i].to,E[i].next,E[i].v);
        for(int i=1;i<=n;++i) 
            printf("head[%d]=%d\n",i,head[i]);
    #endif
        dinic();
        if(ans==tot)puts("^_^");
        else puts("T_T");
    }
    return 0;
} 

扫描二维码,在手机上阅读!
Responses