poj1149

maksyuki 发表于 oj 分类，标签: 图论(网络流)-最大流

15 9月 2015

PIGS

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.

Input

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.

Output

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

Sample Input

3 3

3 1 10

2 1 2 2

2 1 3 3

1 2 6

Sample Output

Source

Croatia OI 2002 Final Exam - First day

题目类型：最大流

算法分析：将每个顾客看做是一个节点，然后对于第一个去猪圈的顾客，将源点和其相连，边权是这个猪圈的初始猪数，对于一个猪圈，之后来的顾客，其与前一个在这个猪圈的顾客相连，权值是INF，最后每个顾客希望得到的最大猪数就是其与汇点相连的边权，建完图之后，直接调用EK算法即可，注意此时源点和汇点分别取值0、n+1

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1000 + 66;


struct Node
{
	int c, f;//分别表示弧之间的容量和流量
};

Node edge[maxn][maxn];
int n, m, pre[maxn], a[maxn];

long long Edmonds_Karp (int s, int t)
{
    queue <int> q;
    memset (a, 0, sizeof(a));
    memset (pre, 0, sizeof(pre));
    long long maxflow = 0;

    while (1)
    {
        memset (a, 0, sizeof(a));
        a[s] = INF;
        q.push(s);
        while (!q.empty())
        {
            int tt = q.front(); q.pop();

            for (int i = 0; i <= n + 1; i++)
            if(!a[i] && edge[tt][i].c > edge[tt][i].f)
            {
                pre[i] = tt;
                q.push (i);
                a[i] = a[tt] < edge[tt][i].c - edge[tt][i].f ? a[tt]:edge[tt][i].c - edge[tt][i].f;
            }
        }

        if(a[t] == 0) break;

        for(int i = t; i != s; i = pre[i])
        {
            edge[pre[i]][i].f += a[t];
            edge[i][pre[i]].f -= a[t];
        }

        maxflow += a[t];
    }
    return maxflow;
}


int pig[maxn], last[maxn];

int main()
{
//    ifstream cin ("aaa.txt");

    while (cin >> m >> n)
	{
		memset (edge, 0, sizeof (edge));
        memset (last, 0, sizeof (last));

        for (int i =1;  i <= m; i++)
            cin >> pig[i];

        for (int i = 1; i <= n; i++)
        {
            int tt;
            cin >> tt;
            for (int j = 1; j <= tt; j++)
            {
                int k;
                cin >> k;
                if (!last[k])
                    edge[0][i].c += pig[k];

                else
                    edge[last[k]][i].c = INF;

                last[k] = i;
            }
            cin >> edge[i][n+1].c;
        }

        cout << Edmonds_Karp (0, n + 1) << endl;
	}

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1000 + 66;

struct Node

{

int c, f;//分别表示弧之间的容量和流量

};

Node edge[maxn][maxn];

int n, m, pre[maxn], a[maxn];

long long Edmonds_Karp (int s, int t)

{

queue <int> q;

memset (a, 0, sizeof(a));

memset (pre, 0, sizeof(pre));

long long maxflow = 0;

while (1)

{

memset (a, 0, sizeof(a));

a[s] = INF;

q.push(s);

while (!q.empty())

{

int tt = q.front(); q.pop();

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

if(!a[i] && edge[tt][i].c > edge[tt][i].f)

{

pre[i] = tt;

q.push (i);

a[i] = a[tt] < edge[tt][i].c - edge[tt][i].f ? a[tt]:edge[tt][i].c - edge[tt][i].f;

}

if(a[t] == 0) break;

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

{

edge[pre[i]][i].f += a[t];

edge[i][pre[i]].f -= a[t];

}

maxflow += a[t];

}

return maxflow;

}

int pig[maxn], last[maxn];

int main()

{

// ifstream cin ("aaa.txt");

while (cin >> m >> n)

{

memset (edge, 0, sizeof (edge));

memset (last, 0, sizeof (last));

for (int i =1; i <= m; i++)

cin >> pig[i];

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

{

int tt;

cin >> tt;

for (int j = 1; j <= tt; j++)

{

int k;

cin >> k;

if (!last[k])

edge[0][i].c += pig[k];

else

edge[last[k]][i].c = INF;

last[k] = i;

}

cin >> edge[i][n+1].c;

}

cout << Edmonds_Karp (0, n + 1) << endl;

}

return 0;

}

poj1144

poj1151

一	二	三	四	五	六	日
« 6月
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

超客的水墨烟雨

poj1149

分类目录

标签云

书签

近期评论