dinic 模板待补充

程序员文章站 2022-05-12 16:35:15

...

#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define pus push_back
#define mo 1005
vector<pair<int ,int > > d[mo];
vector<pair<int ,int > > de[mo];

int tag[mo];

int dfs(int node,int low,int n)
{
  // cout<<node<<endl;

    if(node==n||!low) return low;

    for(int i=0;i<d[node].size();i++)
    {
        int son=d[node][i].first;
        int s=d[node][i].second;
        int flow;
        //cout<<tag[son]<<' '<<tag[node]<<' '<<node<<' '<<son<<" "<<flow<<endl;
        if(tag[son]==tag[node]+1&&(flow=dfs(son,min(low,s),n)))
        {
            //cout<<flow<<endl;
            d[node][i].second-=flow;
            int re=de[node][i].second;
            d[son][re].second+=flow;
            return flow;
        }
    }

    return 0;

}

int bfs(int n)
{
    queue<int > p;

    memset(tag,-1,sizeof(tag));


    p.push(1);
    tag[1]=0;
    int l=0,r=1;

    while(p.size())
    {
        int node=p.front();
        p.pop();

        for(int i=0;i<d[node].size();i++)
        {
            int son=d[node][i].first;
            int se=d[node][i].second;
            if(tag[son]<0&&se>0)
            {
                p.push(son);
                tag[son]=tag[node]+1;
            }
        }
    }
   // cout<<"asd "<<tag[n]<<' '<<n<<endl;
    return tag[n]!=-1;
}

int max_flow(int n)
{
    //cout<<endl;
    int flow;
    int ans=0;
    while( bfs(n) )
    {
        flow=dfs(1,10000000,n);
        /*
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<d[i].size();j++)
            {
                cout<<i<<' '<<d[i][j].first<<' '<<d[i][j].second<<endl;
            }
            cout<<endl;
        }
        */

        ans+=flow;
        //cout<<ans<<' '<<flow<<endl;
    }
    return ans;
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=0;i<mo;i++)
        {
            d[i].clear();
            de[i].clear();
        }
        int x,y,z;
        for(int i=0;i<m;i++)
        {
            cin>>x>>y>>z;
            int a=d[x].size();
            int b=d[y].size();
            de[x].pus(mk(y,b));//我好强
            de[y].pus(mk(x,a));
            d[x].pus(mk(y,z));
            d[y].pus(mk(x,0));
        }
        cout<<max_flow(n)<<endl;
    }

}

#1393 : 网络流三·二分图多重匹配

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

学校的秋季运动会即将开始，为了决定参赛人员，各个班又开始忙碌起来。

小Hi和小Ho作为班上的班*，统计分配比赛选手的重任也自然交到了他们手上。

已知小Hi和小Ho所在的班级一共有N名学生(包含小Hi和小Ho)，编号依次为1..N。

运动会一共有M项不同的比赛，编号为1..M。第i项比赛每个班需要派出m[i]名选手参加。

根据小Hi和小Ho的统计，编号为i的学生表示最多同时参加a[i]项比赛，并且给出他所擅长的b[i]项比赛的编号。

小Hi和小Ho希望将每个学生都安排到他所擅长的比赛项目，以增加夺冠的可能性。同时又要考虑满足每项比赛对人数的要求，当然给一个学生安排的比赛项目也不能超过他愿意参加的比赛项目数量。

根据统计的结果，小Hi和小Ho想知道能否有一个合适的安排，同时满足这些条件。

提示：二分图多重匹配

输入

第1行：1个整数T，表示一共有T(2≤T≤5)组数据，每组数据按如下格式给出：

第1行：2个正整数N,M。1≤N≤100，1≤M≤100。

第2行：M个整数，第i个数表示第i个项目需要的选手数量m[i]。1≤m[i]≤N。

第3..N+2行：若干整数，第i+2行表示编号为i的学生的信息。先是a[i],b[i]，接下来b[i]个整数，表示其所擅长的b[i]个项目。1≤a[i]≤M

输出

第1..T行：第i行表示第i组数据能否满足要求，若能够输出"Yes"，否则输出"No"。

样例输入

样例输出

Yes
No

http://hihocoder.com/problemset/problem/1393

直接使用dinic一直超时- - 然后画图发现一个点会重复走很多次，加一个数组标记之后险过

#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define pus push_back
#define mo 205
vector<pair<int ,int > > d[mo];
vector<pair<int ,int > > de[mo];
int pass[mo];
int tag[mo];

int dfs(int node,int low,int n,int sta,int ent)
{
    if(pass[node]) return 0;
    if(node==ent||!low) return low;
    pass[node]=1;
    int re,son,s,flow=0;
    for(int i=0;i<d[node].size();i++)
    {
        son=d[node][i].first;
        s=d[node][i].second;
        if(tag[son]==tag[node]+1&&(flow=dfs(son,min(low,s),n,sta,ent)))
        {
           // cout<<tag[son]<<' '<<tag[node]<<' '<<node<<' '<<son<<" "<<flow<<endl;
            d[node][i].second-=flow;
            re=de[node][i].second;
            d[son][re].second+=flow;
            if(flow) break;
        }
    }
   // pass[node]=0;
    if(flow) return flow;
    return 0;
}

int bfs(int n,int sta,int ent)
{
    queue<int > p;
    p.push(sta);
    memset(tag,-1,sizeof(tag));
    tag[sta]=0;
    int l=0,r=1,son,se,node;

    while(p.size())
    {
        node=p.front();
        p.pop();

        for(int i=0;i<d[node].size();i++)
        {
            son=d[node][i].first;
            se=d[node][i].second;
            if(tag[son]==-1&&se>0)
            {
                p.push(son);
                tag[son]=tag[node]+1;
                if(son==ent) return 1;
            }
        }
    }
    return 0;
}

int max_flow(int n,int sta,int ent)
{
    int flow;
    int ans=0;
    while( bfs(n,sta,ent)&&(flow=dfs(sta,10000000,n,sta,ent)) )
    {
        memset(pass,0,sizeof(pass));
        ans+=flow;
    }
    return ans;
}
int a,b;
void input(int x,int y,int z)
{
    a=d[x].size();
    b=d[y].size();
    de[x].pus(mk(y,b));//我好强
    de[y].pus(mk(x,a));
    d[x].pus(mk(y,z));
    d[y].pus(mk(x,0));
}
int main()
{
    int t; int n,m,x,y,z,s,sta,ent,sum;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n+m+5;i++)
        {
            d[i].clear();
            de[i].clear();
        }

        sta =n+m+1;
        ent =n+m+2;
        sum=0;

        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            sum+=x;
            input(i,ent,x);
        }

        for(int i=m+1;i<=n+m;i++)
        {
            scanf("%d%d",&s,&y);
            input(sta,i,s);
            for(int j=0;j<y;j++)
            {
                scanf("%d",&x);
                input(i,x,1);
            }
        }

        if(sum==max_flow(ent,sta,ent))
        {
            printf("Yes \n");
        }
        else printf("No \n");
    }
}

#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define pus push_back
#define mo 205

vector<pair<int ,int > > d[mo];
vector<pair<int ,int > > de[mo];

int pass[mo];
int tag[mo];

int dfs(int node,int low,int n,int sta,int ent)
{
    if(pass[node]) return 0;
    if(node==ent||!low) return low;
    pass[node]=1;
    int re,son,s,flow;
    int ans=0;
    for(int i=0;i<d[node].size();i++)
    {
        son=d[node][i].first;
        s=d[node][i].second;
        if(tag[son]==tag[node]+1&&(flow=dfs(son,min(low,s),n,sta,ent)))
        {
            d[node][i].second-=flow;
            re=de[node][i].second;
            d[son][re].second+=flow;
            ans+=flow;
            low-=flow;
            if(!low) break;
        }
    }
    return ans;
}

int bfs(int n,int sta,int ent)
{
    queue<int > p;
    p.push(sta);
    memset(tag,-1,sizeof(tag));
    tag[sta]=0;
    int l=0,r=1,son,se,node;

    while(p.size())
    {
        node=p.front();
        p.pop();

        for(int i=0;i<d[node].size();i++)
        {
            son=d[node][i].first;
            se=d[node][i].second;
            if(tag[son]==-1&&se>0)
            {
                p.push(son);
                tag[son]=tag[node]+1;
                if(son==ent) return 1;
            }
        }
    }
    return 0;
}

int max_flow(int n,int sta,int ent)
{
    int flow;
    int ans=0;
    while( bfs(n,sta,ent)&&(flow=dfs(sta,10000000,n,sta,ent)) )
    {
        memset(pass,0,sizeof(pass));
        ans+=flow;
    }
    return ans;
}
int a,b;
void input(int x,int y,int z)
{
    a=d[x].size();
    b=d[y].size();
    de[x].pus(mk(y,b));//我好强
    de[y].pus(mk(x,a));
    d[x].pus(mk(y,z));
    d[y].pus(mk(x,0));
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n+m+3;i++)
        {
            d[i].clear();
            de[i].clear();
        }

        int  sta =n+m+1;
        int ent =n+m+2;
        int sum=0;
        int s,x,y,z;
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            sum+=x;
            input(i,ent,x);
        }

        for(int i=m+1;i<=n+m;i++)
        {
            scanf("%d%d",&s,&y);
            input(sta,i,s);
            for(int j=0;j<y;j++)
            {
                scanf("%d",&x);
                input(i,x,1);
            }
        }

        if(sum==max_flow(ent,sta,ent))
        {
            printf("Yes \n");
        }
        else printf("No \n");
    }
}

#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define pus push_back
#define mo 1005
vector<pair<int ,int > > d[mo];
vector<pair<int ,int > > de[mo];

int tag[mo];

int dfs(int node,int low,int sta,int ent)
{
    if(node==ent||!low) return low;
    int re,son,s,flow;
    for(int i=0;i<d[node].size();i++)
    {
        son=d[node][i].first;
        s=d[node][i].second;
        if(tag[son]==tag[node]+1&&(flow=dfs(son,min(low,s),sta,ent)))
        {
           // cout<<tag[son]<<' '<<tag[node]<<' '<<node<<' '<<son<<" "<<flow<<endl;
            d[node][i].second-=flow;
            re=de[node][i].second;
            d[son][re].second+=flow;
            return flow;
        }
    }
    return 0;
}

int bfs(int sta,int ent)
{
    queue<int > p;
    p.push(sta);
    memset(tag,-1,sizeof(tag));
    tag[sta]=0;
    int l=0,r=1,son,se,node;

    while(p.size())
    {
        node=p.front();
        p.pop();

        for(int i=0;i<d[node].size();i++)
        {
            son=d[node][i].first;
            se=d[node][i].second;
            if(tag[son]==-1&&se>0)
            {
                p.push(son);
                tag[son]=tag[node]+1;
                if(son==ent) return 1;
            }
        }
    }
    return 0;
}

int max_flow(int sta,int ent)
{
    int flow;
    int ans=0;
    while( bfs(sta,ent)&&(flow=dfs(sta,10000000,sta,ent)) )
    {
        ans+=flow;
        //cout<<flow<<endl;
    }
    return ans;
}

void input(int x,int y,int z)
{
    int a=d[x].size();
    int b=d[y].size();
    de[x].pus(mk(y,b));//我好强
    de[y].pus(mk(x,a));
    d[x].pus(mk(y,z));
    d[y].pus(mk(x,0));
}


int main()
{
    int t; int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<=n;i++)
        {
            d[i].clear();
            de[i].clear();
        }
        int sta =1;
        int ent =n;
        int sum=0;
        int x,y,z;
        for(int i=0;i<m;i++)
        {
            cin>>x>>y>>z;
            input(x,y,z);
        }
        cout<<max_flow(sta,ent)<<endl;

    }
}

上一篇： java 处理时间问题

下一篇： HIbernate 缓存（待补充）

dinic 模板待补充

#1393 : 网络流三·二分图多重匹配

描述

输入

输出

17.网络编程基础知识（待更新补充）

POJ - 1273 Dinic 算法模板

复习篇——网络编程知识点详细总结（待排版，知识点看情况补充

Day 06 模板层补充

HDU 3046 Pleasant sheep and big big wolf（SAP，Dinic模板）