poj3436网络流之最大流拆点

这题看了半天看不懂题意。。。还是看的网上题意写的

加一个源点一个汇点，把每个点拆成两个，这两个点的流量是v，其他联通的边都设为无穷大

输入没有1的点就与源点连接，输出只有1的点就与汇点连接

还有这个输出技巧，因为每条反向弧初始容量设置为0，因此完成增广之后，反向弧的容量即为路径。

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cassert>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define ll long long

#define mod 10007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3fffff;

int a[N][];

int s,t,n,p,pre[N];

bool vis[N];

int c[N][N];

bool bfs()

{

    memset(pre,,sizeof pre);

    memset(vis,,sizeof vis);

    vis[s]=;

    queue<int>q;

    q.push(s);

    while(!q.empty()){

        int x=q.front();

        q.pop();

        if(x==t)return ;

        for(int i=;i<=*n+;i++)

        {

            if(!vis[i]&&c[x][i])

            {

                vis[i]=;

                q.push(i);

                pre[i]=x;

            }

        }

    }

    return ;

}

int max_flow()

{

    int ans=;

    while(){

        if(!bfs())break;

        int minn=inf;

        for(int i=t;i!=s;i=pre[i])

            minn=min(minn,c[pre[i]][i]);

        for(int i=t;i!=s;i=pre[i])

        {

            c[pre[i]][i]-=minn;

            c[i][pre[i]]+=minn;

        }

        ans+=minn;

    }

    cout<<ans<<" ";

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

 //   cout<<setiosflags(ios::fixed)<<setprecision(2);

    while(cin>>p>>n){

        memset(c,,sizeof(c));

        for(int i=;i<=n;i++)

        {

            cin>>c[i][i+n];

            for(int j=;j<=p;j++)cin>>a[i][j];

            for(int j=;j<=p;j++)cin>>a[i+n][j];

        }

        for(int i=;i<=n;i++)

        {

            bool flag=;

            for(int j=;j<=p;j++)

                if(a[i][j]==)

                {

                    flag=;

                    break;

                }

            if(flag)c[][i]=inf;

            flag=;

            for(int j=;j<=p;j++)

                if(a[i+n][j]!=)

                {

                    flag=;

                    break;

                }

            if(flag)c[i+n][*n+]=inf;

        }

        for(int i=n+;i<=*n;i++)//前驱

        {

            for(int j=;j<=n;j++)//后继

            {

                bool flag=;

                for(int l=;l<=p;l++)

                {

                    if(a[j][l]+a[i][l]==)

                    {

                        flag=;

                        break;

                    }

                }

                if(flag)c[i][j]=inf;

            }

        }

    /*    for(int i=0;i<=2*n+1;i++)

        {

            for(int j=0;j<=2*n+1;j++)

                cout<<c[i][j]<<" ";

            cout<<endl;

        }*/

        s=;t=*n+;//t是汇点

        max_flow();

        int cnt=,a1[N],a2[N],a3[N];

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=n;j++)

            {

                if(i!=j&&c[j][i+n]>)

                {

                    ++cnt;

                    a1[cnt]=i;

                    a2[cnt]=j;

                    a3[cnt]=c[j][i+n];

                }

            }

        }

        cout<<cnt<<endl;

        for(int i=;i<=cnt;i++)

            cout<<a1[i]<<" "<<a2[i]<<" "<<a3[i]<<endl;

    }

    return ;

}

巴特西

poj3436网络流之最大流拆点

最新文章

热门文章