写在前面

写完了几道网络流最大流的问题，Dinic算法也练习的差不多了，然后来总结一下网络流的建图问题，毕竟图论的难点不在于算法实现，毕竟有模板可以背，而是在于建图能力，这方面需要提高的。

P1324 晚餐

题目描述：

农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食. 每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料.
农夫JOHN做了F (1 <= F <= 100) 种食品并准备了D (1 <= D <= 100) 种饮料. 他的N (1 <= N <= 100)头牛都以决定了是否愿意吃某种食物和喝某种饮料. 农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料.

输入：

第一行: 三个数: N, F, 和 D
第2..N+1行: 每一行由两个数开始F_i 和 D_i, 分别是第i 头牛可以吃的食品数和可以喝的饮料数.下F_i个整数是第i头牛可以吃的食品号,再下面的D_i个整数是第i头牛可以喝的饮料号码.

输出：

第一行: 一个整数,最多可以喂饱的牛数.

题解：

这道题是非常好的一道题目，拿到这道题，我们是首先想得就是如何进行建图然后计算，这道题我一上来就是将源点连饮品，饮品连牛，然后牛连食物，食物连汇点。然后跑了一遍，卧槽你一个牛吃一堆食物喝一堆饮料干甚！！！

没错上面的建图方式是错误的，因为一个牛的点可能被访问多次，没错就是多次，因为一个牛因为是没有流量限制的，所以说很有可能许多个饮料通过一个牛链接食物，而每个牛只能选择一种饮料和食物。

那么我们就要对牛进行一个限制，也就是通过这个牛的饮料和食物只能是一个，那么最好的方法就是再次建立一层牛，两层牛之间连接一条流量为1的边，那么这就可以限制了通过这个牛的食物和饮料的最大值就是1了。

代码：

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
using namespace std;
struct Edge
{
    int Point;
    int Value;
    int Back;
    int Next;
}a[80000];
int n,m,x,y,z,k,num,len;
int Queue[80000],Maxx,ID,ans;
int Link[80000],Level[80000],all;
inline int In()
{
    int This=0,F=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=This*10+ch-'0';
        ch=getchar();
    }
    return This*F;
}
bool GetLevel()
{
    memset(Level,-1,sizeof(Level));
    int head=0,tail=1;
    Queue[1]=1; Level[1]=0;
    while(++head<=tail)
    {
        for(int i=Link[Queue[head]];i;i=a[i].Next)
        if(Level[a[i].Point]<0&&a[i].Value)
        {
            Queue[++tail]=a[i].Point;
            Level[Queue[tail]]=Level[Queue[head]]+1;
        }
    }
    return Level[Maxx]>=0;
}
int GetMaxFlow(int x,int Flow)
{
    if(x==Maxx) return Flow;
    int MaxFlow=0,D=0;
    for(int i=Link[x];i&&MaxFlow<Flow;i=a[i].Next)
    if(a[i].Value&&Level[a[i].Point]==Level[x]+1)
    if(D=GetMaxFlow(a[i].Point,min(Flow-MaxFlow,a[i].Value)))
    {
        MaxFlow+=D;
        a[i].Value-=D;
        a[a[i].Back].Value+=D;
    }
    if(!MaxFlow) Level[x]=-1;
    return MaxFlow;
}
void Dinic()
{
    int ans;
    while(GetLevel())
    while(ans=GetMaxFlow(1,123456789)) all+=ans;
}
int main()
{
    n=In(); m=In(); k=In();
    Maxx=n*2+m+k+1+1;
    for(int i=1;i<=m;i++)
    {
        a[++len].Point=i+1;
        a[len].Value=1;
        a[len].Next=Link[1];
        a[len].Back=len+1;
        Link[1]=len;
        a[++len].Point=1;
        a[len].Value=0;
        a[len].Next=Link[i+1];
        a[len].Back=len-1;
        Link[i+1]=len;
    }
    for(int i=1;i<=k;i++)
    {
        a[++len].Point=Maxx;
        a[len].Value=1;
        a[len].Next=Link[i+2*n+m+1];
        a[len].Back=len+1;
        Link[Maxx]=len;
        a[++len].Point=i+2*n+m+1;
        a[len].Value=0;
        a[len].Next=Link[Maxx];
        a[len].Back=len-1;
        Link[i+2*n+m+1]=len;
    }
    for(int i=1;i<=n;i++)
    {
        a[++len].Point=m+i+n+1;
        a[len].Value=1;
        a[len].Next=Link[m+i+1];
        a[len].Back=len+1;
        Link[m+i+1]=len;
        a[++len].Point=m+i+1;
        a[len].Value=0;
        a[len].Next=Link[m+i+n+1];
        a[len].Back=len-1;
        Link[m+i+n+1]=len;
    }
    for(int i=1;i<=n;i++)
    {
        int Food,Drank;
        Food=In();Drank=In();
        for(int j=1;j<=Food;j++)
        {
            ID=In();
            a[++len].Point=m+i+1;
            a[len].Value=1;
            a[len].Next=Link[ID+1];
            a[len].Back=len+1;
            Link[ID+1]=len;
            a[++len].Point=ID+1;
            a[len].Value=0;
            a[len].Next=Link[m+i+1];
            a[len].Back=len-1;
            Link[m+i+1]=len;
        }
        for(int j=1;j<=Drank;j++)
        {
            ID=In();
            a[++len].Point=n+n+m+ID+1;
            a[len].Value=1;
            a[len].Next=Link[m+n+i+1];
            a[len].Back=len+1;
            Link[m+n+i+1]=len;
            a[++len].Point=m+n+i+1;
            a[len].Value=0;
            a[len].Next=Link[n+n+m+ID+1];
            a[len].Back=len-1;
            Link[n+n+m+ID+1]=len;
        }
    }
	Dinic();
    cout<<all<<endl;
    return 0;
}

P1609 Pigs

题目描述：

尼克在一家养猪场工作，这家养猪场共有M间锁起来的猪舍，由于猪舍的钥匙都给了客户，所以尼克没有办法打开这些猪舍，客户们从早上开始一个接一个来购买生猪，他们到达后首先用手中的钥匙打开他所能打开的全部猪舍，然后从中选取他要买的生猪，尼克可以在此期间将打开的猪舍中的猪调整到其它开着的猪舍中，每个猪舍能存放的猪的数量是没有任何限制的。买完猪后客户会将他打开的猪舍关上。
好在尼克事先知道每位客户手中有哪些钥匙，要买多少猪，以及客户到来的先后次序。请你写一个程序，帮助尼克求出最多能卖出多少头生猪。

输入：

输入文件的第一行包含两个整数M和N，1≤M≤1000，1≤N≤100，M为猪舍的数量，N为客户人数，猪舍的编号为1到M，客户的编号为1到N。
输入文件第二行包含M个空格隔开的整数，依次表示每个猪舍中的生猪数量，每个整数大于等于0，且小于等于1000。
接下来的N行每行表示一位客户的购买信息，第I个客户的购买信息位于第I+2行，它表示该客户共有A把钥匙，钥匙编号依次为K1 K2……KA，且K1<K2<……<KA，B为该客户要买的生猪的头数。

输出：

输出文件仅有一行包含一个整数，表示尼克最多能卖出的生猪的头数。

题解：

这道题的建图简直是丧心病狂的难，首先拿到题目之后你会发现，这个建图怎么搞。首先访问是有顺序的，而且最重要的是，每个猪栏之间如果是同时打开的，还会交换，也就是说，一般的建图方法就是没有办法解出来的。

那么我们该怎么办呢，猪栏之间的流通怎么转换，而且顾客的访问是有顺序的。所以我们必须在顾客身上想办法。

那么我们可以将顾客之间连接一条无穷大的边，而且是后面的通过前面的，这样才能符合题目要求，那么具体要怎么做呢，首先我们建立一个源点一排顾客和一个汇点，猪栏就可以省掉了。读入每个顾客链接的猪栏，如果是第一个打开这个猪栏的，那么建造一条最大流为猪栏内猪的大小的边，连接顾客。然后如果这个猪栏别人已经开过了，就可以连接第一个开这个栏的人，这样通过这个人就可以在当前这个猪栏买到猪，而且这也符合了同时打开的猪栏可以交换的要求（通过连接的那个顾客访问当时可以打开的猪栏等价于交换）

最后我们只需要将顾客和汇点建立一条流大小为顾客购买的猪的数量的边，最后跑一遍Dinic算法就好（话说Dinic有时候真的很容易敲错，需要不停的练习）

代码：

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
using namespace std;
struct Edge
{
    int Point;
    int Next;
    int Back;
    int Value;
}a[40000];
int n,m,Queue[40000],num;
int Link[40000],len,Maxx;
int c[4000],ans,all;
int Level[40000],X,Y,Z;
int vis[20000],Pig[2000];
inline int In()
{
    int This=0,F=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=This*10+ch-'0';
        ch=getchar();
    }
    return This*F;
}
bool GetLevel()
{
    memset(Level,-1,sizeof(Level));
    int head=0,tail=1;
    Queue[1]=1; Level[1]=0;
    while(++head<=tail)
    {
        for(int i=Link[Queue[head]];i;i=a[i].Next)
        if(Level[a[i].Point]<0&&a[i].Value)
        {
            Queue[++tail]=a[i].Point;
            Level[Queue[tail]]=Level[Queue[head]]+1;
        }
    }
    return Level[Maxx]>=0;
}
int GetMaxFlow(int x,int Flow)
{
    if(x==Maxx) return Flow;
    int MaxFlow=0,D=0;
    for(int i=Link[x];i&&MaxFlow<Flow;i=a[i].Next)
    if(a[i].Value&&Level[a[i].Point]==Level[x]+1)
    if(D=GetMaxFlow(a[i].Point,min(Flow-MaxFlow,a[i].Value)))
    {
        MaxFlow+=D;
        a[i].Value-=D;
        a[a[i].Back].Value+=D;
    }
    if(!MaxFlow) Level[x]=-1;
    return MaxFlow;
}
void Dinic()
{
    while(GetLevel())
    while(ans=GetMaxFlow(1,123456789))
    all+=ans;
    cout<<all<<endl;
}
void initFirst(int x,int y,int z)
{
    a[++len].Point=y;
    a[len].Value=z;
    a[len].Back=len+1;
    a[len].Next=Link[x];
    Link[x]=len;
}
void initSecond(int x,int y,int z)
{
    a[++len].Point=y;
    a[len].Value=z;
    a[len].Back=len-1;
    a[len].Next=Link[x];
    Link[x]=len;
}
int main()
{
    m=In(); n=In();
    Maxx=n+2;
    for(int i=1;i<=m;i++) Pig[i]=In();
    for(int i=1;i<=n;i++)
    {
        Z=In();
        for(int j=1;j<=Z;j++)
        {
            Y=In();
            if(!vis[Y])
            {
                initFirst(1,i+1,Pig[Y]);
                initSecond(i+1,1,0);
            }
            else
            {
                initFirst(vis[Y],i+1,123456789);
                initSecond(i+1,vis[Y],0);
            }
            vis[Y]=i+1;
        }
        Z=In();
        initFirst(i+1,Maxx,Z);
        initSecond(Maxx,i+1,0);
    }
    Dinic();
    return 0;
}