Loading...

洛谷P1129 [ZJOI2007]矩阵游戏

check评论:0 条 remove_red_eye浏览量:453 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-19

二分图网络流真是一家亲

因为本蒟蒻不会匈牙利

所以我又来水最大流了qwq

我们先设立源点$s$为$0$,向每一行连边,每一列向汇点$t$为$2\times n +1$连边

然后如果$i$行$j$列是$1$,我们就从第$i$行向第$j$列连边

如果最大流大于等于$n$,就可以了qwq

#include <bits/stdc++.h>
using namespace std;
int head[50050],dis[50050],vis[50050];
struct edge
{
    int next,to,dis;
}e[200010];
int cnt=1,cur[50010],n;
void add(int u,int v,int dis)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=dis;
    head[u]=cnt;
}
int s=0,t;
int bfs()
{
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memcpy(cur,head,sizeof(head));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]==-1&&e[i].dis>0)
            {
                dis[v]=dis[u]+1;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return dis[t]!=-1;
}
int dfs(int u,int exp)
{
    if(u==t||!exp)
    {
        return exp;
    }
    int flow=0;
    for(int i=cur[u];i;i=e[i].next)
    {
        cur[u]=i;
        int v=e[i].to;
        if(dis[v]==dis[u]+1&&e[i].dis>0)
        {
            int tmp=dfs(v,min(exp,e[i].dis));
            if(!tmp)
            {
                continue;
            }
            exp-=tmp;
            flow+=tmp;
            e[i].dis-=tmp;
            e[i^1].dis+=tmp;
            if(!exp)
            {
                break;
            }
        }
    }
    return flow;
}
int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        memset(e,0,sizeof(e));
        memset(head,0,sizeof(head));
        memset(cur,0,sizeof(cur));
        cin>>n;
        t=(n<<1)+1;
        for(int i=1;i<=n;i++)
        {
            add(s,i,1);
            add(i,s,0);
            add(i+n,t,1);
            add(t,i+n,0);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int x;
                scanf("%d",&x);
                if(x)
                {
                    add(i,j+n,1);
                    add(j+n,i,0);
                }
            } 
        }
        int ans=0;
        while(bfs())
        {
            ans+=dfs(s,0x3f3f3f3f);
        }
        if(ans>=n)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl; 
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名