网络流、最大流

源点S和汇点T，每条有向边的有一个权值，成为边的容量c(x,y)；若(x,y)不属于E，则c(x,y)=0；
f(x,y)表示边(x,y)上的流量，c(x,y)-f(x,y)称为边的剩余容量；
最大流：从源点流向汇点的最大流量
增广路：一条从源点到汇点的所有变得剩余容量>=0得路径
残留网:由网络中所有节点和剩余容量大于0的变构成的子图；
构建反向边的目的是提供一个"退流管道",提供了"后悔机制"

P3376 【模板】网络最大流

EK()算法，复杂度为O(nmm),一般可达：n=1000,m=10000,实际所用更小

借用大佬图片： 算法流程如下

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
struct edge
{
    int to,c,nxt;
}e[N];
int n,m,s,t;
int head[N],idx=1;
int mf[N],pre[N];
void add(int a,int b,int c)
{
    e[++idx]={b,c,head[a]};
    head[a]=idx;
}
bool bfs()
{
    for(int i=0;i<=n;i++)
        mf[i]=0;
    queue<int>q;
    q.push(s);
    mf[s]=inf;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(mf[v]==0&&e[i].c)
            {
                mf[v]=min(mf[u],e[i].c);
                pre[v]=i;
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int EK()
{
    int flow=0;
    while(bfs())
    {
        int v=t;
        while(v!=s)
        {
            int i=pre[v];
            e[i].c-=mf[t];
            e[i^1].c+=mf[t];
            v=e[i^1].to;
        }
        flow+=mf[t];
    }
    return flow;
}
void solve()
{
    cin>>n>>m>>s>>t;
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);add(v,u,0);
    }
    cout<<EK()<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

P2740 [USACO4.2]草地排水Drainage Ditches

思路：从源点到汇点，在满足各条边可承受的容量条件下，可留过的最大流量是多少，采用EK()算算，构造残缺图
代码：

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
struct edge
{
    int to,c,nxt;
}e[N];
int n,m,s,t;
int head[N],idx=1;
int mf[N],pre[N];
void add(int a,int b,int c)
{
    e[++idx]={b,c,head[a]};
    head[a]=idx;
}
bool bfs()
{
    for(int i=0;i<=n;i++)
        mf[i]=0;
    queue<int>q;
    q.push(s);
    mf[s]=inf;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(mf[v]==0&&e[i].c)
            {
                mf[v]=min(mf[u],e[i].c);
                pre[v]=i;
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int EK()
{
    int flow=0;
    while(bfs())
    {
        int v=t;
        while(v!=s)
        {
            int i=pre[v];
            e[i].c-=mf[t];
            e[i^1].c+=mf[t];
            v=e[i^1].to;
        }
        flow+=mf[t];
    }
    return flow;
}
void solve()
{
    cin>>n>>m;
    s=1,t=m;
    for(int i=1,u,v,w;i<=n;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);add(v,u,0);
    }
    cout<<EK()<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

P1343 地震逃生

思路：
1.可套网络流模板。算出地震时在各个楼道可承受人数的条件下，求出最大逃生人数
2.再根据x总人数，算出可分的批次，答案为(x+ans-1)/x .算一道板子题
代码：

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
struct edge
{
    int to,c,nxt;
}e[N];
int n,m,s,t,x;
int head[N],idx=1;
int mf[N],pre[N];
void add(int a,int b,int c)
{
    e[++idx]={b,c,head[a]};
    head[a]=idx;
}
bool bfs()
{
    for(int i=0;i<=n;i++)
        mf[i]=0;
    queue<int>q;
    q.push(s);
    mf[s]=inf;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(mf[v]==0&&e[i].c)
            {
                mf[v]=min(mf[u],e[i].c);
                pre[v]=i;
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int EK()
{
    int flow=0;
    while(bfs())
    {
        int v=t;
        while(v!=s)
        {
            int i=pre[v];
            e[i].c-=mf[t];
            e[i^1].c+=mf[t];
            v=e[i^1].to;
        }
        flow+=mf[t];
    }
    return flow;
}
void solve()
{
    cin>>n>>m>>x;
    s=1,t=n;
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);add(v,u,0);
    }
    int ans=EK();
    if(ans==0)
    {
        cout<<"Orz Ni Jinan Saint Cow!"<<endl;return;
    }
    cout<<ans<<" "<<(x+ans-1)/ans<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

P2763 试题库问题

思路：
1.采用二分图的思路。若所选类型的题目类型都可找到自身匹配的题目，即匹配数==cnt(要求题目数）
2.左部点为要求题目类型的数量，为虚点；右部点为具体的题目。二者连线，进行最大匹配

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int k,n,head[N],idx,cnt,cnt2,num[25],tag[N];
int match[N],used[N],ans;
vector<int>v[N],res[N];
struct node
{
    int to,nxt;
}e[N];
void add(int from,int to)
{
    e[++idx].to=to;
    e[idx].nxt=head[from];
    head[from]=idx;
}
int dfs(int u)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(!used[v])
        {
            used[v]=1;
            if(match[v]==-1||dfs(match[v]))
            {
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
void hungary()
{
    memset(match,-1,sizeof(match));
    for(int i=1;i<=n;i++)
    {
        memset(used,0,sizeof used);
        if(dfs(i))
            ans++;
    }
}

void solve()
{
    cin>>k>>n;
    for(int i=1;i<=k;i++)
    {
        cin>>num[i];
        cnt+=num[i];
    }
    for(int i=1;i<=n;i++)
    {
        int p;cin>>p;
        for(int j=1;j<=p;j++)
        {
            int a;cin>>a;
            v[a].push_back(i);  //类型->题目
        }
    }
    for(int i=1;i<=k;i++)       //类型->题目
    {
        for(int j=1;j<=num[i];j++)
        {
            tag[++cnt2]=i;      //类型
            for(int g:v[i])     //题目
            {
                add(cnt2,g);
            }
        }
    }
    hungary();
    cout<<ans<<endl;
    if(ans<cnt)
    {
        cout<<"No Solution!"<<endl;return;
    }
    for(int i=1;i<=n;i++)
        res[tag[match[i]]].push_back(i);
    for(int i=1;i<=k;i++)
    {
        cout<<i<<": ";
        for(int j:res[i])
            cout<<j<<" ";
        cout<<endl;
    }
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103