8.23网络流专项训练题解

发表于 | 分类于 ， | 热度 ℃
字数统计: 9,439 | 阅读时长 ≈ 45

问题 A: 赛马

时间限制: 1 Sec 内存限制: 128 MB
提交: 32 解决: 5
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

古有田忌赛马戏齐王，今有悠悠赛马虐渣渣。悠悠和他的小老弟渣渣每人有n匹马，每匹马都有一个评分，分数越高速度越快。现在渣渣不甘于当小老弟，随着赛马曲的想起，渣渣决定挑战悠悠，规则同田忌赛马。每胜一局得1分，每负一局减一分，赵神做裁判，悠悠为了捍卫自己的王者地位，决定出老千，问了赵神关于渣渣的赛马顺序，请问悠悠最高能得多少分。

输入

文件有多组测试样例，遇0为止。

首行一个整数n，n<=1000;

第2行n个整数表示悠悠每匹马的分数。

第3行n个整数表示渣渣每匹马的分数。0<=分数<500;

输出

输出悠悠最高分。

样例输入

1
2
3
4
5
6
7
8
9
10
3
192 173 71
195 177 74
2
10 10
10 10
2
220 219
222 218
0

样例输出

1
2
3
1
0
0

提示

水题，可以用网络流或者匹配，也可以用更简单的方法。

[提交][状态][Edit][TestData)]

题解

本题贪心可解。贪心策略即田忌赛马的策略。第1步我们将我们最慢的马和对方最快的马进行比较，如果最慢的马比对方最慢的马快，那么我们就胜一局，然后返回第1步。反之我们进行第2步，继续拿我们最快的马和对方最快的马进行比较，如果获胜就胜一局，然后返回第1步。反之我们进行第3步，继续拿我们最慢的马和对方最快的马进行比较，这种情况下分为两种情况，一种是得分相等，另外一种是我方必败，必败得分减一，否则不变，然后我们再返回第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
#include<bits/stdc++.h>
using namespace std;
int a[1007],b[1007];
int main(){
	freopen("input.txt","r",stdin);
    int n;
    while(cin>>n){
    	if(n==0)
    		break;
        for(int i=0; i<n; i++)
            cin>>a[i];
        for(int i=0; i<n; i++)
            cin>>b[i];
        sort(a,a+n);
        sort(b,b+n);
        int s=0;
        for(int i=0,j=0,k=n-1,l=n-1; i<=k;){
            if(a[i]>b[j])
            	s++,i++,j++;
            else if(a[k]>b[l])
            	s++,k--,l--;
            else{
                if(a[i]<b[l])
                	s--;
                i++,l--;
            }
        }
        cout<<s<<endl;
    }
    return 0;
}

问题 B: 海上钢琴师

时间限制: 1 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

宁愿一生孤独，不愿随波逐流。海上钢琴师毅然留在了船上，与大海为伴，此生再不上岸。

然而，他的音乐却已名扬四海。为了将他的钢琴声可以传播到陆地以便欣赏，人们决定在陆地与钢琴师所在的船之间的n-2座岛屿上建立声音保留设备。每当声音传到该设备处时，以该设备为起点可以将声音信号发送到其他与该设备有信号连接的设备那里。信号传播是单向的，且是有限的。当该设备将一部分信号传给其他设备时，该设备所拥有的总信号要减去相应传出去的信号，所保留的信号可以继续传给其他的设备。船上也有该设备，由于岛屿与船的位置不同，所以钢琴声传到设备的声音有限。设备与设备之间的传播分贝也有限。陆地的总接收设备与某些岛屿上的设备有信号连接，请问陆地最多能收到多少分贝的钢琴声。

输入

第一行输入两个数m，n。m代表共有m对设备建立了单向连接。n代表包括船和陆地在内共有n个设备。编号1为船，编号n为陆地，其他为岛屿（n<=100，m<=1000）

接下来m行，每行三个数a，b，c，代表a->b，即a的信号可以传到b信号，最大可以通过该信号传送c分贝。c<=2000

输出

输出陆地上最大可以收到多少分贝声音。（海上钢琴声不超过10000分贝）

样例输入

1
2
3
4
5
6
5 4
1 2 100
1 3 50
2 3 2
3 4 60
2 4 99

样例输出

1
150

提示

样例解释：（容量，流量）

方案1：

img

方案2：

img

[提交][状态][Edit][TestData)]

题解

网络流最大流模板题。题面转化过来就是一个网络流模型，船为s，陆地为t，设备之间的连接就是弧。用FF算法，EK算法，Dinic算法，SAP算法，预流推进，均可解。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=200+7;
const int inf=0x3f3f3f3f;
int r[maxn][maxn]; //残留网络，初始化为原图
bool visit[maxn];
int pre[maxn];
int m,n;
bool bfs(int s,int t)  //寻找一条从s到t的增广路，若找到返回true
{
    int p;
    queue<int > q;
    memset(pre,-1,sizeof(pre));
    memset(visit,false,sizeof(visit));

    pre[s]=s;
    visit[s]=true;
    q.push(s);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(r[p][i]>0&&!visit[i])
            {
                pre[i]=p;
                visit[i]=true;
                if(i==t) return true;
                q.push(i);
            }
        }
    }
    return false;
}

int EdmondsKarp(int s,int t)
{
   int flow=0,d,i;
   while(bfs(s,t))
   {
       d=inf;
       for(i=t;i!=s;i=pre[i])
           d=d<r[pre[i]][i]? d:r[pre[i]][i];
       for(i=t;i!=s;i=pre[i])
       {
           r[pre[i]][i]-=d;
           r[i][pre[i]]+=d;
       }
       flow+=d;
   }
   return flow;
}


int main()
{
	freopen("input.txt","r",stdin);
    while(cin>>m>>n)
    {
        int u,v,w;
        memset(r,0,sizeof(r));
        for(int i=0;i<m;i++)
        {
        	cin>>u>>v>>w;
            r[u][v]+=w;
        }
        cout<<EdmondsKarp(1,n)<<endl;
    }
    return 0;
}

问题 C: 进击的巨人

时间限制: 1 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

那一年，巨人发起了第一轮进击，s城破，埃尔文团长带领众居民计划逃往较安全的t城。从s城到t城之间共有m坐城市，某些城市之间构成单向通路。由s城到t城恰构成一个有向无环图。然而每条路上都有限定的最大人流量。埃尔文团长想知道每一次最多有多少居民能到达t城。

输入

首行输入两个数n，m（n，m<=100），n0为s城，nn为t城。s城到t城之间的城用n1——nn表示。m表示单项通道数。

接下来m行，每行三个数a，b，c，代表a到b的最大人流量是c。c<1000。

输出

输出最多有多少人到t

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
6 14
0 2 5
0 1 10
1 2 6
0 3 5
3 1 2
1 5 3
5 2 3
5 4 3
3 5 3
3 4 4
3 6 5
2 6 6
4 6 10
2 4 4

样例输出

1
18

[提交][状态][Edit][TestData)]

题解

网络流最大流模板题。用FF算法，EK算法，Dinic算法，SAP算法，预流推进，均可解。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=200+7;
const int inf=0x3f3f3f3f;
int r[maxn][maxn]; //残留网络，初始化为原图
bool visit[maxn];
int pre[maxn];
int m,n;
bool bfs(int s,int t)  //寻找一条从s到t的增广路，若找到返回true
{
    int p;
    queue<int > q;
    memset(pre,-1,sizeof(pre));
    memset(visit,false,sizeof(visit));

    pre[s]=s;
    visit[s]=true;
    q.push(s);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(r[p][i]>0&&!visit[i])
            {
                pre[i]=p;
                visit[i]=true;
                if(i==t) return true;
                q.push(i);
            }
        }
    }
    return false;
}

int EdmondsKarp(int s,int t)
{
   int flow=0,d,i;
   while(bfs(s,t))
   {
       d=inf;
       for(i=t;i!=s;i=pre[i])
           d=d<r[pre[i]][i]? d:r[pre[i]][i];
       for(i=t;i!=s;i=pre[i])
       {
           r[pre[i]][i]-=d;
           r[i][pre[i]]+=d;
       }
       flow+=d;
   }
   return flow;
}


int main()
{
	freopen("input.txt","r",stdin);
    while(cin>>n>>m)
    {
        int u,v,w;
        memset(r,0,sizeof(r));
        for(int i=0;i<m;i++)
        {
        	cin>>u>>v>>w;
            r[u][v]+=w;
        }
        cout<<EdmondsKarp(0,n)<<endl;
    }
    return 0;
}

问题 D: X档案

时间限制: 1 Sec 内存限制: 128 MB
提交: 5 解决: 3
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

据X档案记载，倘若外星文明即将攻击地球，会在战争之前发动病毒袭击，最合理的对象是鸟或狗，因为鸟在空中传播病毒的范围2较广，而狗相较于其他动物来说和人类接触最频繁。X城作为全球反外星文明的重要基地，对外星文明来说威胁最大而作为外星文明首先攻击的目标。因此，X长官下令捕杀了全城的鸟，而狗由于受到爱狗人士们的保护免于此劫。然而灾难还是降临了，外星文明悄无声息地将病毒注入到一些狗体内。据全球卫星显示，X城的地形是一个nm的矩阵，划分成了nm个11的小矩阵。矩阵的四周被城墙所围。而在某些单位11的小矩阵中有居民，或者有被感染的狗。我们已经知道了狗的全部坐标，为了安全起见，X长官启动了X计划，将这些狗在未发作之前用围栏隔离起来以防止狗攻击人类，每个1*1的小矩阵四周均可建立围栏。该计划收录到了X档案中。围栏使得狗和人类均无法通过。由于计划的机密性，长官不想动用太多的财力，现求最少需要多长围栏才能将所有狗隔离。

输入

输入包含多组样例，读到文件结束。

第一行为n，m，代表n*m的矩阵。（0<n，m<=150）

接下来n行，每行m个由0，1，2组成的数。

0代表此处没有任何东西，1代表此处有人，2代表此处有被感染的狗。

输出

输出格式为：Case i: k

i为第i组样例，k为所需最短的围栏长度。

样例输入

1
2
3
4
5
6
7
8
9
10
11
5 6
0 0 0 1 0 0
2 0 0 0 0 1
0 0 1 0 0 0
0 0 2 0 0 1
0 0 0 1 0 0
4 6
0 0 1 0 0 1
0 0 0 1 1 0
0 0 0 0 2 2
0 1 1 0 2 0

样例输出

1
2
Case 1: 6
Case 2: 4

提示

第1组样例解释：

img

第2组样例解释：

img

[提交][状态][Edit][TestData)]

题解

题目描述那么多，其实就是最小割问题。只不过我们要建立一个超级源点指向所有狼（羊），再建立一个超级汇点指向所有羊（狼）。羊和狼为结点，两个节点直接一条边，权值为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
#include<bits/stdc++.h>
#define maxn 100100
#define inf 0x3f3f3f3f
using namespace std;
int to[maxn],c[maxn],first[maxn],Next[maxn],N;
int d[maxn];
int Q[maxn],bot,top,tag[maxn],can[maxn];
int s,t,n,m,tmp,ans,cas=0;
int TAG=5201314;
void _init()
{
    ans=s=0,t=n*m+1,N=-1;
    for (int i=s; i<=t; i++) first[i]=-1;
}
void edge(int U,int V,int W)
{
    N++;
    to[N]=V,c[N]=W;
    Next[N]=first[U],first[U]=N;
}
void _input()
{
    int cur=0;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            scanf("%d",&tmp);
            cur++;
            if (i<n) edge(cur,cur+m,1),edge(cur+m,cur,1);
            if (j<m) edge(cur,cur+1,1),edge(cur+1,cur,1);
            if (tmp==2) edge(s,cur,inf),edge(cur,s,inf);
                else if (tmp==1) edge(cur,t,inf),edge(t,cur,inf);
        }

}
bool bfs()
{
    TAG++;
    Q[bot=top=1]=t,d[t]=0,tag[t]=TAG;
    while (bot<=top)
    {
        int cur=Q[bot++];
        for (int i=first[cur]; i!=-1; i=Next[i])
        {
            if (c[i^1]<=0 || tag[to[i]]==TAG) continue;
            tag[to[i]]=TAG,d[to[i]]=d[cur]+1,Q[++top]=to[i];
            if (to[i]==s) return true;
        }
    }
    return false;
}

int dfs(int cur,int num)
{
    if (cur==t) return num;
    int tmp=num,k;
    for (int i=first[cur]; i!=-1; i=Next[i])
    {
        if (d[cur]!=d[to[i]]+1 || c[i]<=0 || tag[to[i]]!=TAG || can[to[i]]==TAG) continue;
        k=dfs(to[i],min(num,c[i]));
        if (k) c[i]-=k,c[i^1]+=k,num-=k;
        if (num==0) break;
    }
    if (num) can[cur]=TAG;
    return tmp-num;
}
void dinic(){
    while (bfs())
    	ans+=dfs(s,inf);
}
int main()
{
	freopen("input.txt","r",stdin);
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        _init();
        _input();
        dinic();
        printf("Case %d: %d\n",++cas,ans);
    }
    return 0;
}

问题 E: 同桌的你

时间限制: 1 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

据yoyo统计，青春期的情侣80%都是曾经的同桌。因此，选择好的同桌对你日后的感情发展有很大的帮助。高一7班共有n个男生，m个女生，男生们听过分析后纷纷要求重新排座位，以期待和心仪的女生做同桌。每个男生都有自己的暗恋对象，0<=暗恋对象的个数<=m，也就是说某个男生最多暗恋全班女生，最少一个都不暗恋。汪老师知道这件事后很是重视，于是开始调座位，优先考虑男生和他的暗恋女生坐在一起。男生用a表示，女生用n表示。请问最多有多少男生能和自己心仪的对象坐在一起。

输入

首行输入n，m，e（0<n，m<=1000，0<=e<=10000）n男m女e为所有男生暗恋女生的个数之和。

接下来e行，每行两个数i，j，代表ai男生暗恋bj女生。

输出

一个整数，最优分配下最多有多少男生能和自己心仪的对象坐在一起。

样例输入

1
2
3
2 1 2
2 1
1 1

样例输出

1
1

提示

样例解释：

全班两个男生暗恋班里唯一一个女生，无论怎么分配只能凑成一对。

[提交][状态][Edit][TestData)]

题解

二分图最大匹配问题。男生和女生构成二分图，每个男生和暗恋的女生之间建立一条边。由于不涉及到权值，因此可用匈牙利算法求解，当然也可用网络流求解。网络流的话就是在二分图的两部分分别建立超级源点s和超级汇点t，每条边的容量固定是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
#include<bits/stdc++.h>
using namespace std;
int n,m;
int cnt=2;
int alist[6000001];
struct data{
    int v;int next;int value;
}edge[6000001];
void add(int u,int v,int value)
{
    edge[cnt].v=v;
    edge[cnt].value=value;
    edge[cnt].next=alist[u];
    alist[u]=cnt++;
    return ;
}
int h[1000001];
int q[1000001];
bool bfs()
{
    int x,next;
    memset(h,-1,sizeof(h));
    int head=0,tail=1;
    q[head]=1;
    h[1]=0;
    while(head<tail)
    {
        x=q[head++];
        next=alist[x];
        while(next)
        {
            int v=edge[next].v;
            int value=edge[next].value;
            if(value&&h[v]<0)
            {
                q[tail++]=v;
                h[v]=h[x]+1;
            }
            next=edge[next].next;
        }
    }
    if(h[n]==-1) return false;
    return true;
}
int ans;
int dfs(int x,int y)
{
    if(x==n) return y;
    int next=alist[x];
    int w,used=0;
    while(next)
    {
        int v=edge[next].v;
        int value=edge[next].value;
        if(value&&h[v]==h[x]+1)
        {
                w=y-used;
                w=dfs(v,min(w,value));
                edge[next].value-=w;
                edge[next^1].value+=w;
                used+=w;
                if(used==y) return y;
        }
        next=edge[next].next;
    }
    if(!used) h[x]=-1;
    return used;
}
void dinic()
{
    while(bfs()) ans+=dfs(1,0x7fffffff);
}
int n1,m1,e1;
int main()
{
	freopen("input.txt","r",stdin);
    scanf("%d%d%d",&n1,&m1,&e1);
    n=n1+m1+2;
    for(int i=1;i<=n1;i++)
    {
        add(1,i+1,1);
        add(i+1,1,1);
    }
    for(int i=1;i<=e1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(u<=n1&&v<=m1)
        add(u+1,v+n1+1,1),
        add(v+n1+1,u+1,1);
    }
    for(int i=1;i<=m1;i++)
    {
        add(i+n1+1,n,1);
        add(n,i+n1+1,1);
    }
    dinic();//暴力跑最大流
    printf("%d",ans);
    return 0;
}

问题 F: 奇迹暖暖

时间限制: 1 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

梅拉抢走了绫罗的设计图，暖暖决定帮绫罗抢过来。于是梅拉和暖暖开始了搭配比赛。梅拉和暖暖各有n套衣服。由于暖暖是天才服装搭配师，且自带主角光环，又怎会输呢，（废话，输了你怎么通关啊）只不过暖暖为了让梅拉输的心服口服，决定狠狠虐梅拉一把。针对梅拉的n套衣服，暖暖的每套衣服i得分都比梅拉的任意一套衣服j得分高出score(ij)，0<=score(ij)<100000。然而每比完一场，他们之后的比赛都不能再用这套的衣服了。所以对于n场比赛，求出暖暖最高能比梅拉高多少分？（至少为0）

输入

首行输入n(n<=300)

接下来n行，第i行表示暖暖的第i套衣服，每行n个数，第j个数表示暖暖第i套衣服比梅拉第j套衣服的分高多少分。

0<=score(ij)<100000

输出

输出一个整数，即最高高出多少分

样例输入

1
2
3
2
100 5
20 23

样例输出

1
123

[提交][状态][Edit][TestData)]

题解

最大权二分图匹配。暖暖和梅拉构成二分图。每条边均有权值，最终求解二分匹配下的最大权值。二分图匹配除了网络流以外还有两道专门解二分图的算法，即匈牙利算法和KM算法。匈牙利算法一般解决二分图最大匹配问题，即边没有权值。而km算法一般解决有权值的二分图。本题为KM算法模板题。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int N=300+7;
const int INF=0x3f3f3f3f;
int n,nx,ny;
int linker[N],lx[N],ly[N],slack[N];
int visx[N],visy[N],w[N][N];

int DFS(int x){
    visx[x]=1;
    for(int y=1;y<=ny;y++){
        if(visy[y])
            continue;
        int tmp=lx[x]+ly[y]-w[x][y];
        if(tmp==0){
            visy[y]=1;
            if(linker[y]==-1 || DFS(linker[y])){
                linker[y]=x;
                return 1;
            }
        }else if(slack[y]>tmp){
            slack[y]=tmp;
        }
    }
    return 0;
}
int KM(){
    int i,j;
    memset(linker,-1,sizeof(linker));
    memset(ly,0,sizeof(ly));
    for(i=1;i<=nx;i++)      //lx初始化为与它关联边中最大的
        for(j=1,lx[i]=-INF;j<=ny;j++)
            if(w[i][j]>lx[i])
                lx[i]=w[i][j];
    for(int x=1;x<=nx;x++){
        for(i=1;i<=ny;i++)
            slack[i]=INF;
        while(1){
            memset(visx,0,sizeof(visx));
            memset(visy,0,sizeof(visy));
            if(DFS(x))  //若成功（找到了增广轨），则该点增广完成，进入下一个点的增广
                break;  //若失败（没有找到增广轨），则需要改变一些点的标号，使得图中可行边的数量增加。
                        //方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，
                        //所有在增广轨中的Y方点的标号全部加上一个常数d
            int d=INF;
            for(i=1;i<=ny;i++)
                if(!visy[i] && d>slack[i])
                    d=slack[i];
            for(i=1;i<=nx;i++)
                if(visx[i])
                    lx[i]-=d;
            for(i=1;i<=ny;i++)  //修改顶标后，要把所有不在交错树中的Y顶点的slack值都减去d
                if(visy[i])
                    ly[i]+=d;
                else
                    slack[i]-=d;
        }
    }
    int res=0;
    for(i=1;i<=ny;i++)
        if(linker[i]!=-1)
            res+=w[linker[i]][i];
    return res;
}

int main(){
	freopen("input.txt","r",stdin);
    while(~scanf("%d",&n)){
        nx=ny=n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&w[i][j]);
        int ans=KM();
        printf("%d\n",ans);
    }
    return 0;
}

问题 G: 巨人也疯狂

时间限制: 1 Sec 内存限制: 128 MB
提交: 2 解决: 2
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

人类发现巨人控制吃人的神经是由一些神经元和一些神经通道组成的，每个神经通道两端各有一个神经元，且这个通道是单向的。吃人信号从脑部神经元S发出到控制吃人的神经元T，S、T之间是一个有向无环图。人类想把某些神经通道切断达到S的信号无法传到T（由于神经元太小不容易砍掉，所以考虑神经元），每个神经通道由于位置不同也有砍断所需的力量。人类想知道如何花最小的力气而使S的信号传不到T。

输入

首行输入两个数，n，m，（n，m<1000）。n代表包括s，t在内共有n个节点，1为s，n为t。

接下来m行，每行3个数，a，b，c，表示a到b的神经通路需要花费c力气。

输出

输出最小的力气。

样例输入

1
2
3
4
5
6
7
8
9
7 8
1 2 2
1 3 2
2 4 2
2 5 2
3 5 2
4 6 2
6 7 2
5 7 2

样例输出

1
4

[提交][状态][Edit][TestData)]

题解

网络流最小割模板题。根据最小割最大流定理，求最小割问题即求最大流问题。用FF算法，EK算法，Dinic算法，SAP算法，预流推进，均可解。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=200+7;
const int inf=0x3f3f3f3f;
int r[maxn][maxn]; //残留网络，初始化为原图
bool visit[maxn];
int pre[maxn];
int m,n;
bool bfs(int s,int t)  //寻找一条从s到t的增广路，若找到返回true
{
    int p;
    queue<int > q;
    memset(pre,-1,sizeof(pre));
    memset(visit,false,sizeof(visit));

    pre[s]=s;
    visit[s]=true;
    q.push(s);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(r[p][i]>0&&!visit[i])
            {
                pre[i]=p;
                visit[i]=true;
                if(i==t) return true;
                q.push(i);
            }
        }
    }
    return false;
}

int EdmondsKarp(int s,int t)
{
   int flow=0,d,i;
   while(bfs(s,t))
   {
       d=inf;
       for(i=t;i!=s;i=pre[i])
           d=d<r[pre[i]][i]? d:r[pre[i]][i];
       for(i=t;i!=s;i=pre[i])
       {
           r[pre[i]][i]-=d;
           r[i][pre[i]]+=d;
       }
       flow+=d;
   }
   return flow;
}


int main()
{
	freopen("input.txt","r",stdin);
    while(cin>>n>>m)
    {
        int u,v,w;
        memset(r,0,sizeof(r));
        for(int i=0;i<m;i++)
        {
        	cin>>u>>v>>w;
            r[u][v]+=w;
        }
        cout<<EdmondsKarp(0,n)<<endl;
    }
    return 0;
}

问题 H: 过河拆桥

时间限制: 1 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

猴子是一种自私的动物。动物世界由河流分成了n个岛屿。这天，猴子在a1岛屿上望见an岛屿上有一片桃林。a1到an之间有n-2个岛屿，分别是a2——an-1。岛屿之间共有m坐桥，每座桥都有一定的距离。现在猴子通过这些桥从a1走到了an，然而由于猴子怕其他动物也过去享受那片桃林，于是每走一座桥都会拆一座桥。终于到了an，吃完桃子后，正直涨潮，于是他必须马上回到a1，由于之前走过的桥被拆了，所以只能寻找一条新的路回到a1。请问猴子从a1到an，再从an回到a1的最短路径是多少。

输入

首行输入nm（n<=1000m<=10000）

接下来m行，每行三个数x，y，z，代表ax岛与ay岛之间有桥，距离是z。（z<=35000）

输出

输出一个整数，为最短距离。

样例输入

1
2
3
4
5
6
4 5
2 3 1
2 4 2
1 2 1
3 4 1
1 3 2

样例输出

1
6

[提交][状态][Edit][TestData)]

题解

最小费用最大流问题。本题可以转化为从1到n找两条不重边的路，使得这两条路的距离之和加起来相对于其他方案来说最小。转化成功之后就是建模过程。首先以1为源点，n为汇点。边的长度就是每条边的费用，每条边的容量为1。由于我们要找两条路到达t，那么我们s点的流量就必须是2，这样流到t点的最大流最大为2，为1证明无解，为2即有解。然而由于源点流量一般无限大，那么我们只需再建立一个超级源点sss，和源点s相连，且容量为2，当然sss到s的费用为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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,cap,cost ,rev;
};
int V;
vector<edge>G[maxn];
int dist[maxn];
int prevv[maxn],preve[maxn];
void add(int from,int to,int cap,int cost)
{
    edge e,w;
    e.to=to;
    e.cap=cap;
    e.cost=cost;
    e.rev=G[to].size();
    G[from].push_back(e);
    w.to=from;
    w.cap=0;
    w.cost=-cost;
    w.rev=G[from].size()-1;
    G[to].push_back(w);
}
int min_ans(int s,int t,int f)
{
    int res=0;

    while(f>0)
    {
        for(int i=0; i<V; i++)
        {
            dist[i]=inf;
        }
        dist[s]=0;
        bool update=true;
        while(update)
        {

            update=false;
            for(int v=0; v<V; v++)
            {
                if(dist[v]==inf)
                {
                    continue;
                }
                for(int i=0; i<G[v].size(); i++)
                {
                    edge &e=G[v][i];
                    if(e.cap>0&&dist[e.to]>dist[v]+e.cost)
                    {
                        dist[e.to]=dist[v]+e.cost;
                        prevv[e.to]=v;
                        preve[e.to]=i;
                        update=true;
                    }
                }
            }
        }
        if(dist[t]==inf)
            return -1;
        int d=f;
        for(int v=t; v!=s; v=prevv[v])
        {
            d=min(d,G[prevv[v]][preve[v]].cap);
        }
        f-=d;
        res+=d*dist[t];
        for(int v=t; v!=s; v=prevv[v])
        {
            edge &e =G[prevv[v]][preve[v]];
            e.cap-=d;
            G[v][e.rev].cap+=d;
        }
    }
    return res;
}
int N,M;
int main()
{
	freopen("input.txt","r",stdin);
    int a,b,c;
    while(cin>>N>>M)
    {
        V=N;
        for(int i=0; i<=N; i++)
            G[i].clear();
        for(int i=0; i<M; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            a--;
            b--;
            add(a,b,1,c);
            add(b,a,1,c);
        }
        printf("%d\n",min_ans(0,N-1,2));
    }
    return 0;
}

问题 I: 植物大战僵尸

时间限制: 1 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

Plants vs. Zombies（PVZ）是最近十分风靡的一款小游戏。Plants（植物）和Zombies（僵尸）是游戏的主角，其中Plants防守，而Zombies进攻。该款游戏包含多种不同的挑战系列，比如Protect Your Brain、Bowling等等。其中最为经典的，莫过于玩家通过控制Plants来防守Zombies的进攻，或者相反地由玩家通过控制Zombies对Plants发起进攻。

现在，我们将要考虑的问题是游戏中Zombies对Plants的进攻，请注意，本题中规则与实际游戏有所不同。游戏中有两种角色，Plants和Zombies，每个Plant有一个攻击位置集合，它可以对这些位置进行保护；而Zombie进攻植物的方式是走到植物所在的位置上并将其吃掉。

游戏的地图可以抽象为一个N行M列的矩阵，行从上到下用0到N–1编号，列从左到右用0到M–1编号；在地图的每个位置上都放有一个Plant，为简单起见，我们把位于第r行第c列的植物记为Pr c。

Plants分很多种，有攻击类、防守类和经济类等等。为了简单的描述每个Plant，定义Score和Attack如下：

Score[Pr c]

Zombie击溃植物Pr c可获得的能源。若Score[Pr c]为非负整数，则表示击溃植物Pr c可获得能源Score[Pr c]，若为负数表示击溃Pr c需要付出能源 -Score[Pr c]。

Attack[Pr c]

植物Pr c能够对Zombie进行攻击的位置集合。

Zombies必须从地图的右侧进入，且只能沿着水平方向进行移动。Zombies攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此Zombies的进攻总是从地图的右侧开始。也就是说，对于第r行的进攻，Zombies必须首先攻击Pr M-1；若需要对Pr c（0≤c<M-1）攻击，必须将PrM-1 Pr M-2 … Pr c+1先击溃，并移动到位置(r c)才可进行攻击。

在本题的设定中，Plants的攻击力是无穷大的，一旦Zombie进入某个Plant的攻击位置，该Zombie会被瞬间消灭，而该Zombie没有时间进行任何攻击操作。因此，即便Zombie进入了一个Plant所在的位置，但该位置属于其他植物的攻击位置集合，则Zombie会被瞬间消灭而所在位置的植物则安然无恙（在我们的设定中，Plant的攻击位置不包含自身所在位置，否则你就不可能击溃它了）。

Zombies的目标是对Plants的阵地发起进攻并获得最大的能源收入。每一次，你可以选择一个可进攻的植物进行攻击。本题的目标为，制定一套Zombies的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。

输入

输入的第一行包含两个整数N M，分别表示地图的行数和列数。

接下来N×M行描述每个位置上植物的信息。第r×M + c + 1行按照如下格式给出植物Pr c的信息：第一个整数为Score[Pr c] 第二个整数为集合Attack[Pr c]中的位置个数w，接下来w个位置信息（r’ c’），表示Pr c可以攻击位置第r’ 行第c’ 列。

输出

输出仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。

样例输入

1
2
3
4
5
6
7
3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0

样例输出

1
25

[提交][状态][Edit][TestData)]

题解

最大权闭合图问题。最大权闭合图转化为最小割问题，再由最小割转化成最大流问题。课件上有详解。

（本题作为NOI的考试题，同时也是今天十道题中最难的一道题，是不是顿时感觉到了自己与高中生们的差距(ó﹏ò｡)ε=(´ο｀*)))唉）

代码

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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define M 1000
using namespace std;
int now,tot,s,t,va[M],du[M],H[M],h[M],ok[M],d[M],v[M],cur[M];
int n,m;
queue<int> q;
struct edge1
{
	int x,y,ne;
}e[500000];
struct edge
{
	int from,to,cap,flow,ne;
}E[500000];
int C(int x,int y)
{
	return (x-1)*m+y;
}
void Add(int x,int y)
{
	e[++tot].y=y;
	e[tot].x=x;
	e[tot].ne=H[x];
	H[x]=tot;
	du[y]++;
}
void Addedge(int from,int to,int cap)
{
	E[++tot]=(edge){from,to,cap,0,h[from]};
	h[from]=tot;
	E[++tot]=(edge){to,from,0,0,h[to]};
	h[to]=tot;
}
bool bfs()
{
	for (int i=s;i<=t;i++)
		v[i]=0;
	v[s]=1;
	d[s]=0;
	q.push(s);
	while (!q.empty())
	{
		int x=q.front();
		q.pop();
		for (int i=h[x];i;i=E[i].ne)
		{
			edge e=E[i];
			if (!v[e.to]&&e.cap>e.flow)
			{
				v[e.to]=1;
				d[e.to]=d[x]+1;
				q.push(e.to);
			}
		}
	}
	return v[t];
}
int dfs(int x,int a)
{
	if (x==t||!a) return a;
	int flow=0;
	for (int &i=cur[x];i;i=E[i].ne)
	{
		edge &e=E[i];
		if (d[e.to]!=d[x]+1) continue;
		int f=dfs(e.to,min(a,e.cap-e.flow));
		if (f)
		{
			flow+=f;
			a-=f;
			e.flow+=f;
			E[i^1].flow-=f;
			if (!a) break;
		}
	}
	return flow;
}
int dinic()
{
	int flow=0;
	while (bfs())
	{
		for (int i=s;i<=t;i++)
			cur[i]=h[i];
		flow+=dfs(s,inf);
	}
	return flow;
}
void Topsort()
{
	queue<int> q;
	for (int i=1;i<=now;i++)
		if (!du[i]) ok[i]=1,q.push(i);
	while (!q.empty())
	{
		int x=q.front();
		q.pop();
		for (int i=H[x];i;i=e[i].ne)
		{
			int y=e[i].y;
			du[y]--;
			if (!du[y])
			{
				ok[y]=1;
				q.push(y);
			}
		}
	}
}
int main()
{
	freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			now++;
			int w;
			scanf("%d%d",&va[now],&w);
			for (int k=1;k<=w;k++)
			{
				int x,y;
				scanf("%d%d",&x,&y);
				x++,y++;
				Add(now,C(x,y));
			}
			if (j!=m) Add(now+1,now);
		}
	Topsort();
	s=0,t=now+1;
	int ans=0;
	tot=1;
	for (int x=1;x<=now;x++)
		if (ok[x])
		{
			if (va[x]>0) ans+=va[x],Addedge(s,x,va[x]);
			else Addedge(x,t,-va[x]);
			for (int i=H[x];i;i=e[i].ne)
			{
				int y=e[i].y;
				if (ok[y])
					Addedge(y,x,inf);
			}
		}
	cout<<ans-dinic()<<endl;
	return 0;
}

问题 J: Pigs

时间限制: 1 Sec 内存限制: 128 MB
提交: 2 解决: 2
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

Mirko works on a pig farm that consists of M locked pig-houses and Mirko can’t unlock any pighouse because he doesn’t have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.
All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold.
More precisely the procedure is as following: the customer arrives opens all pig-houses to which he has the key Mirko sells a certain number of pigs from all the unlocked pig-houses to him and if Mirko wants he can redistribute the remaining pigs across the unlocked pig-houses.
An unlimited number of pigs can be placed in every pig-house.
Write a program that will find the maximum number of pigs that he can sell on that day.

输入

The first line of input contains two integers M and N 1 <= M <= 1000 1 <= N <= 100 number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.
The next line contains M integeres for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 … KA B It means that this customer has key to the pig-houses marked with the numbers K1 K2 … KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0.

输出

The first and only line of the output should contain the number of sold pigs.

样例输入

1
2
3
4
5
3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6

样例输出

1
7

[提交][状态][Edit][TestData)]

题解

课件上有建模讲解。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int N=107,M=1007,INF=0x3f3f3f3f;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}

int m,n,s,t;
int pig[M],now[M];
struct edge{
    int v,c,f,ne;
}e[N*M<<1];
int cnt,h[N];
inline void ins(int u,int v,int c){
    cnt++;
    e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt;
    cnt++;
    e[cnt].v=u;e[cnt].c=0;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt;
}
int q[N],head,tail,vis[N],d[N];
bool bfs(){
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));
    head=tail=1;
    d[s]=0;vis[s]=1;
    q[tail++]=s;
    while(head!=tail){
        int u=q[head++];
        for(int i=h[u];i;i=e[i].ne){
            int v=e[i].v;
            if(!vis[v]&&e[i].c>e[i].f){
                vis[v]=1;
                d[v]=d[u]+1;
                q[tail++]=v;
                if(v==t) return true;
            }
        }
    }
    return false;
}
int cur[N];
int dfs(int u,int a){
    if(u==t||a==0) return a;
    int flow=0,f;
    for(int &i=cur[u];i;i=e[i].ne){
        int v=e[i].v;
        if(d[v]==d[u]+1&&(f=dfs(v,min(a,e[i].c-e[i].f)))>0){
            flow+=f;
            e[i].f+=f;
            e[((i-1)^1)+1].f-=f;
            a-=f;
            if(a==0) break;
        }
    }
    return flow;
}
int dinic(){
    int flow=0;
    while(bfs()){
        for(int i=s;i<=t;i++) cur[i]=h[i];
        flow+=dfs(s,INF);
    }
    return flow;
}
int main(){
	freopen("input.txt","r",stdin);
    m=read();
    n=read();
    s=0;
    t=n+1;
    for(int i=1;i<=m;i++)
    	pig[i]=read();
    for(int i=1;i<=n;i++){
        int A=read(),B,x;
        while(A--){
            x=read();
            if(!now[x]) ins(s,i,pig[x]),now[x]=i;
            else ins(now[x],i,INF),now[x]=i;
        }
        B=read();
        ins(i,t,B);
    }
    printf("%d",dinic());
}
文章结束了，但我们的故事还在继续
坚持原创技术分享，您的支持将鼓励我继续创作！