4月 | 2016 | 超客的水墨烟雨

poj1742

maksyuki 发表于 oj 分类，标签: DP-背包

16 4月 2016

Coins

People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.

Input

The input contains several test cases. The first line of each test case contains two integers n(1<=n<=100),m(m<=100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1<=Ai<=100000,1<=Ci<=1000). The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

Sample Output

Source

LouTiancheng@POJ

题目类型：多重背包

算法分析：dp[i]表示容量为i的背包是否会被填满，则按照每种物品的数量进行对应的操作即可，不过总时间复杂度是O(NVlogV)的，复杂度比较高

/*************************************************
Author        :supermaker
Created Time  :2016/4/15 21:07:41
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 666;

int c[maxn], m[maxn], N, M;
bool dp[100000+maxn];

void zero (int c)
{
	for (int i = M; i >= c; i--)
		dp[i] |= dp[i-c];
}

void comp (int c)
{
	for (int i = c; i <= M; i++)
		dp[i] |= dp[i-c];
}

void SS (int c, int m)
{
	if (c * m >= M) comp (c);
	else
	{
		int k = 1;
		while (k < m)
		{
			zero (k * c);
			m -= k;
			k *= 2; 
		}
		zero (m * c);
	}
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &N, &M) != EOF)
	{
		if (N == 0 && M == 0) break;
		for (int i = 1; i <= N; i++)
			scanf ("%d", &c[i]);
		for (int i = 1; i <= N; i++)
			scanf ("%d", &m[i]);

		memset (dp, 0, sizeof (dp));
		dp[0] = true;
		for (int i = 1; i <= N; i++)
			SS (c[i], m[i]);
		int res = 0;
		for (int i = 1; i <= M; i++)
			if (dp[i])
				res++;
		printf ("%d\n", res);
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

/*************************************************

Author :supermaker

Created Time :2016/4/15 21:07:41

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 666;

int c[maxn], m[maxn], N, M;

bool dp[100000+maxn];

void zero (int c)

{

for (int i = M; i >= c; i--)

dp[i] |= dp[i-c];

}

void comp (int c)

{

for (int i = c; i <= M; i++)

dp[i] |= dp[i-c];

}

void SS (int c, int m)

{

if (c * m >= M) comp (c);

else

{

int k = 1;

while (k < m)

{

zero (k * c);

m -= k;

k *= 2;

}

zero (m * c);

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &N, &M) != EOF)

{

if (N == 0 && M == 0) break;

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

scanf ("%d", &c[i]);

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

scanf ("%d", &m[i]);

memset (dp, 0, sizeof (dp));

dp[0] = true;

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

SS (c[i], m[i]);

int res = 0;

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

if (dp[i])

res++;

printf ("%d\n", res);

}

return 0;

}

算法分析：一个复杂度是O(NV)的算法是用dp[i]表示容量为i的背包是否会被填满，sum[j]表示组成容积为j的背包所需要第i种物品的数量。最后对于每个物品遍历求解一遍即可

/*************************************************
Author        :supermaker
Created Time  :2016/4/16 20:16:26
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

int c[166], m[166], sum[maxn];
bool dp[maxn];

int main()
{
    //CFF;
    //CPPFF;
	int N, M;
	while (scanf ("%d%d", &N, &M) != EOF)
	{
		if (N == 0 && M == 0) break;
		for (int i = 1; i <= N; i++)
			scanf ("%d", &c[i]);
		for (int i = 1; i <= N; i++)
			scanf ("%d", &m[i]);

		memset (dp, false, sizeof (dp));
		dp[0] = true;
		int res = 0;
		for (int i = 1; i <= N; i++)
		{
			memset (sum, 0, sizeof (sum));
			for (int j = c[i]; j <= M; j++)
				if (!dp[j] && dp[j-c[i]] && sum[j-c[i]] < m[i])
				{
					dp[j] = true;
					sum[j] = sum[j-c[i]] + 1;
					res++;
				}
		}
		printf ("%d\n", res);
	}
    return 0;
}

/*************************************************

Author :supermaker

Created Time :2016/4/16 20:16:26

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 66;

int c[166], m[166], sum[maxn];

bool dp[maxn];

int main()

{

//CFF;

//CPPFF;

int N, M;

while (scanf ("%d%d", &N, &M) != EOF)

{

if (N == 0 && M == 0) break;

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

scanf ("%d", &c[i]);

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

scanf ("%d", &m[i]);

memset (dp, false, sizeof (dp));

dp[0] = true;

int res = 0;

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

{

memset (sum, 0, sizeof (sum));

for (int j = c[i]; j <= M; j++)

if (!dp[j] && dp[j-c[i]] && sum[j-c[i]] < m[i])

{

dp[j] = true;

sum[j] = sum[j-c[i]] + 1;

res++;

}

printf ("%d\n", res);

}

return 0;

}

poj3280

maksyuki 发表于 oj 分类，标签: DP-区间DP

15 4月 2016

Cheapest Palindrome

Keeping track of all the cows can be a tricky task so Farmer John has installed a system to automate it. He has installed on each cow an electronic ID tag that the system will read as the cows pass by a scanner. Each ID tag's contents are currently a single string with length M (1 ≤ M ≤ 2,000) characters drawn from an alphabet of N (1 ≤ N ≤ 26) different symbols (namely, the lower-case roman alphabet).

Cows, being the mischievous creatures they are, sometimes try to spoof the system by walking backwards. While a cow whose ID is "abcba" would read the same no matter which direction the she walks, a cow with the ID "abcb" can potentially register as two different IDs ("abcb" and "bcba").

FJ would like to change the cows's ID tags so they read the same no matter which direction the cow walks by. For example, "abcb" can be changed by adding "a" at the end to form "abcba" so that the ID is palindromic (reads the same forwards and backwards). Some other ways to change the ID to be palindromic are include adding the three letters "bcb" to the begining to yield the ID "bcbabcb" or removing the letter "a" to yield the ID "bcb". One can add or remove characters at any location in the string yielding a string longer or shorter than the original string.

Unfortunately as the ID tags are electronic, each character insertion or deletion has a cost (0 ≤ cost ≤ 10,000) which varies depending on exactly which character value to be added or deleted. Given the content of a cow's ID tag and the cost of inserting or deleting each of the alphabet's characters, find the minimum cost to change the ID tag so it satisfies FJ's requirements. An empty ID tag is considered to satisfy the requirements of reading the same forward and backward. Only letters with associated costs can be added to a string.

Input

Line 1: Two space-separated integers: N and M
Line 2: This line contains exactly M characters which constitute the initial ID string
Lines 3..N+2: Each line contains three space-separated entities: a character of the input alphabet and two integers which are respectively the cost of adding and deleting that character.

Output

Line 1: A single line with a single integer that is the minimum cost to change the given name tag.

Sample Input

3 4
abcb
a 1000 1100
b 350 700
c 200 800

Sample Output

900

Hint

If we insert an "a" on the end to get "abcba", the cost would be 1000. If we delete the "a" on the beginning to get "bcb", the cost would be 1100. If we insert "bcb" at the begining of the string, the cost would be 350 + 200 + 350 = 900, which is the minimum.

Source

USACO 2007 Open Gold

题目类型：区间DP

算法分析：dp[i][j]表示区间[i,j]内的字符串变成回文串需要的最小花费。dp[i][i] = 0, 若s[i] == s[j]，则易知此时dp[i][j] = dp[i+1][j-1]，因为此时字符串首尾两端已经满足回文的条件，只需要中间也满足即可。反之则dp[i][j] = min (dp[i+1][j] + cost[s[i]-‘a’], dp[i][j-1] + cost[s[j]-‘a’])。因为任意回文串在其首尾添加或删除一对相同的字符会构造出新的回文串

/*************************************************
Author        :supermaker
Created Time  :2016/4/15 20:31:47
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

char s[maxn];
int cost[66], dp[maxn][maxn];

int main()
{
    //CFF;
    //CPPFF;
	int n, m;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		scanf (" %s", s + 1);
		for (int i = 1; i <= n; i++)
		{
			char id;
			int u, v;
			scanf (" %c %d %d", &id, &u, &v);
			cost[id-'a'] = min (u, v);
		}
		memset (dp, 0, sizeof (dp));
		for (int len = 1; len <= m; len++)
			for (int i = 1; i <= m; i++)
			{
				int j = i + len;
				if (j > m) break;
				if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1];
				else dp[i][j] = min (dp[i+1][j] + cost[s[i]-'a'], dp[i][j-1] + cost[s[j]-'a']);
			}
		printf ("%d\n", dp[1][m]);
	}
    return 0;
}

/*************************************************

Author :supermaker

Created Time :2016/4/15 20:31:47

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 2000 + 66;

char s[maxn];

int cost[66], dp[maxn][maxn];

int main()

{

//CFF;

//CPPFF;

int n, m;

while (scanf ("%d%d", &n, &m) != EOF)

{

scanf (" %s", s + 1);

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

{

char id;

int u, v;

scanf (" %c %d %d", &id, &u, &v);

cost[id-'a'] = min (u, v);

}

memset (dp, 0, sizeof (dp));

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

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

{

int j = i + len;

if (j > m) break;

if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1];

else dp[i][j] = min (dp[i+1][j] + cost[s[i]-'a'], dp[i][j-1] + cost[s[j]-'a']);

}

printf ("%d\n", dp[1][m]);

}

return 0;

}

poj2718

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

15 4月 2016

Smallest Difference

Given a number of distinct decimal digits, you can form one integer by choosing a non-empty subset of these digits and writing them in some order. The remaining digits can be written down in some order to form a second integer. Unless the resulting integer is 0, the integer may not start with the digit 0.

For example, if you are given the digits 0, 1, 2, 4, 6 and 7, you can write the pair of integers 10 and 2467. Of course, there are many ways to form such pairs of integers: 210 and 764, 204 and 176, etc. The absolute value of the difference between the integers in the last pair is 28, and it turns out that no other pair formed by the rules above can achieve a smaller difference.

Input

The first line of input contains the number of cases to follow. For each case, there is one line of input containing at least two but no more than 10 decimal digits. (The decimal digits are 0, 1, ..., 9.) No digit appears more than once in one line of the input. The digits will appear in increasing order, separated by exactly one blank space.

Output

For each test case, write on a single line the smallest absolute difference of two integers that can be written from the given digits as described by the rules above.

Sample Input

1
0 1 2 4 6 7

Sample Output

Source

Rocky Mountain 2005

题目类型：DFS搜索

算法分析：要想保证得到的是最小距离，需要满足两个数的位数尽量接近。所以dfs枚举得到lena / 2位的数vala，然后再构造valb，然后对于组成valb的数字枚举序列并更新最小值

/*************************************************
Author        :supermaker
Created Time  :2016/4/15 19:37:46
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

int aa[maxn], bb[maxn], lena, lenb, tt, res;
bool vis[maxn];

void SS (int val)
{
	lenb = tt = 0;
	for (int i = 1; i <= lena; i++)
		if (!vis[i])
			bb[++lenb] = aa[i], tt = tt * 10 + aa[i];

	if (bb[1] > 0 || lenb == 1)
		res = min (res, abs (val - tt));

	while (next_permutation (bb + 1, bb + 1 + lenb))
	{
		if (bb[1] > 0 || lenb == 1)	
		{
			tt = 0;
			for (int i = 1; i <= lenb; i++)
				tt = tt * 10 + bb[i];
			res = min (res, abs (val - tt));
		}
	}
}

void dfs (int cur, int val)
{
	if (cur == lena / 2)
	{
		SS (val);
		return ;
	}

	for (int i = 1; i <= lena; i++)
		if (!vis[i])
		{
			if (cur == 0 && aa[i] == 0 && lena >= 4) continue;
			vis[i] = true;
			dfs (cur + 1, val * 10 + aa[i]);
			vis[i] = false;
		}
}

int main()
{
    //CFF;
    //CPPFF;
	int t;
	cin >> t;
	string s;
	getline (cin, s);
	while (t--)
	{
		getline (cin, s);
		stringstream ss (s);
		lena = 0;
		while (ss >> aa[++lena]) ;
		lena--;
		memset (vis, false, sizeof (vis));
		res = INF;
		dfs (0, 0);
		cout << res << endl;
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

/*************************************************

Author :supermaker

Created Time :2016/4/15 19:37:46

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 10 + 66;

int aa[maxn], bb[maxn], lena, lenb, tt, res;

bool vis[maxn];

void SS (int val)

{

lenb = tt = 0;

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

if (!vis[i])

bb[++lenb] = aa[i], tt = tt * 10 + aa[i];

if (bb[1] > 0 || lenb == 1)

res = min (res, abs (val - tt));

while (next_permutation (bb + 1, bb + 1 + lenb))

{

if (bb[1] > 0 || lenb == 1)

{

tt = 0;

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

tt = tt * 10 + bb[i];

res = min (res, abs (val - tt));

}

void dfs (int cur, int val)

{

if (cur == lena / 2)

{

SS (val);

return ;

}

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

if (!vis[i])

{

if (cur == 0 && aa[i] == 0 && lena >= 4) continue;

vis[i] = true;

dfs (cur + 1, val * 10 + aa[i]);

vis[i] = false;

}

int main()

{

//CFF;

//CPPFF;

int t;

cin >> t;

string s;

getline (cin, s);

while (t--)

{

getline (cin, s);

stringstream ss (s);

lena = 0;

while (ss >> aa[++lena]) ;

lena--;

memset (vis, false, sizeof (vis));

res = INF;

dfs (0, 0);

cout << res << endl;

}

return 0;

}

poj3262

maksyuki 发表于 oj 分类，标签: 基础算法-贪心

14 4月 2016

Protecting the Flowers

Farmer John went to cut some wood and left N (2 ≤ N ≤ 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cluster of cows was in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action and transport each cow back to its own barn.

Each cow i is at a location that is T_i minutes (1 ≤ T_i ≤ 2,000,000) away from its own barn. Furthermore, while waiting for transport, she destroys D_i (1 ≤ D_i ≤ 100) flowers per minute. No matter how hard he tries, FJ can only transport one cow at a time back to her barn. Moving cow i to its barn requires 2 × T_i minutes (T_i to get there and T_i to return). FJ starts at the flower patch, transports the cow to its barn, and then walks back to the flowers, taking no extra time to get to the next cow that needs transport.

Write a program to determine the order in which FJ should pick up the cows so that the total number of flowers destroyed is minimized.

Input

Line 1: A single integer N
Lines 2..N+1: Each line contains two space-separated integers, T_i and D_i, that describe a single cow's characteristics

Output

Line 1: A single integer that is the minimum number of destroyed flowers

Sample Input

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

Sample Output

Hint

FJ returns the cows in the following order: 6, 2, 3, 4, 1, 5. While he is transporting cow 6 to the barn, the others destroy 24 flowers; next he will take cow 2, losing 28 more of his beautiful flora. For the cows 3, 4, 1 he loses 16, 12, and 6 flowers respectively. When he picks cow 5 there are no more cows damaging the flowers, so the loss for that cow is zero. The total flowers lost this way is 24 + 28 + 16 + 12 + 6 = 86.

Source

USACO 2007 January Silver

题目类型：贪心

算法分析：对于序列中相邻的两个奶牛A和B，若A在B之前，则加入后的总费用Asum为(sumd - Ad) * 2At + (sumd - Ad - Bd) * 2Bt，若B在前，则总费用Bsum为(sumd - Bd) * 2Bt + (sumd - Bd - Ad) * 2At，其中sumd表示当前还没有被运输的奶牛单位时间的总损害量。若A要在B的前面，则需要满足Asum < Bsum，则将上式代入后化简得Bd / Bt < Ad / At，即单位时间损害量大的要先被拿走

/*************************************************
Author        :supermaker
Created Time  :2016/4/14 8:42:28
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

struct Node
{
	LL t, d;
	double k;
	bool operator < (const Node &a) const
	{
		return k > a.k;
	}
};

Node aa[maxn];

int main()
{
    //CFF;
    //CPPFF;
   	int n;
	while (scanf ("%d", &n) != EOF)
	{
		LL sumd = 0;
		for (int i = 1; i <= n; i++)
		{
			scanf ("%lld%lld", &aa[i].t, &aa[i].d);
			aa[i].k = aa[i].d * 1.0 / aa[i].t;
			sumd += aa[i].d;
		}
		sort (aa + 1, aa + 1 + n);
		
		LL res = 0;
		for (int i = 1; i <= n; i++)
		{
			res += (sumd - aa[i].d) * 2 * aa[i].t;
			sumd -= aa[i].d;	
		}
		printf ("%lld\n", res);
	}
    return 0;
}

/*************************************************

Author :supermaker

Created Time :2016/4/14 8:42:28

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

struct Node

{

LL t, d;

double k;

bool operator < (const Node &a) const

{

return k > a.k;

}

};

Node aa[maxn];

int main()

{

//CFF;

//CPPFF;

int n;

while (scanf ("%d", &n) != EOF)

{

LL sumd = 0;

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

{

scanf ("%lld%lld", &aa[i].t, &aa[i].d);

aa[i].k = aa[i].d * 1.0 / aa[i].t;

sumd += aa[i].d;

}

sort (aa + 1, aa + 1 + n);

LL res = 0;

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

{

res += (sumd - aa[i].d) * 2 * aa[i].t;

sumd -= aa[i].d;

}

printf ("%lld\n", res);

}

return 0;

}

poj3040

maksyuki 发表于 oj 分类，标签: 基础算法-贪心

12 4月 2016

Allowance

As a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different 阅读全文 »

poj3187

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化, 组合数学-计数

12 4月 2016

Backward Digit Sums

FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N=4) might go like this:

3   1   2   4
4   3   6
7   9
16

Behind FJ's back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately, the game is a bit above FJ's mental arithmetic capabilities.

Write a program to help FJ play the game and keep up with the cows.

Input

Line 1: Two space-separated integers: N and the final sum.

Output

Line 1: An ordering of the integers 1..N that leads to the given sum. If there are multiple solutions, choose the one that is lexicographically least, i.e., that puts smaller numbers first.

Sample Input

4 16

Sample Output

3 1 2 4

Hint

Explanation of the sample:

There are other possible sequences, such as 3 2 1 4, but 3 1 2 4 is the lexicographically smallest.

Source

USACO 2006 February Gold & Silver

题目类型：序列枚举+组合计数

算法分析：从小到大按照字典序生成序列，然后对于每个序列计算相邻和，简单观察会发现最后的和是Sigma(C(n - 1, i - 1) * a[i])，不需要模拟计算

/*************************************************
Author        :supermaker
Created Time  :2016/4/12 12:38:57
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int aa[16], com[16][16];

void getCom ()
{
	memset (com, 0, sizeof (com));
	for (int i = 0; i <= 10; i++)
		for (int j = 0; j <= i; j++)
		{
			if (!j || i == j) com[i][j] = 1;
			else com[i][j] = com[i-1][j-1] + com[i-1][j];
		}
	com[0][0] = 0;
}

int main()
{
    //CFF;
    //CPPFF;
   	int n, val;
	getCom ();
	while (scanf ("%d%d", &n, &val) != EOF)
	{
		for (int i = 1; i <= n; i++)
			aa[i] = i;
		
		int tt;
		do
		{
			tt = aa[1] + aa[n];
			for (int i = 2; i <= n - 1; i++)
				tt += com[n-1][i-1] * aa[i];
			if (tt == val) break;
		} while (next_permutation (aa + 1, aa + 1 + n));

		for (int i = 1; i <= n; i++)
		{
			if (i == 1) printf ("%d", aa[i]);
			else printf (" %d", aa[i]);
		}
		puts ("");
	}
    return 0;
}

/*************************************************

Author :supermaker

Created Time :2016/4/12 12:38:57

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int aa[16], com[16][16];

void getCom ()

{

memset (com, 0, sizeof (com));

for (int i = 0; i <= 10; i++)

for (int j = 0; j <= i; j++)

{

if (!j || i == j) com[i][j] = 1;

else com[i][j] = com[i-1][j-1] + com[i-1][j];

}

com[0][0] = 0;

}

int main()

{

//CFF;

//CPPFF;

int n, val;

getCom ();

while (scanf ("%d%d", &n, &val) != EOF)

{

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

aa[i] = i;

int tt;

{

tt = aa[1] + aa[n];

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

tt += com[n-1][i-1] * aa[i];

if (tt == val) break;

} while (next_permutation (aa + 1, aa + 1 + n));

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

{

if (i == 1) printf ("%d", aa[i]);

else printf (" %d", aa[i]);

}

puts ("");

}

return 0;

}

BestCoder Round #78(Div.2) (0/4) (Div.1) (0/4)

maksyuki 发表于比赛分类，标签: 比赛-bestcoder

09 4月 2016

poj1966

maksyuki 发表于 oj 分类，标签: 图论(网络流)-最大流, 图论(网络流)-最小割, 图论-求解连通度

09 4月 2016

Cable TV Network

The interconnection of the relays in a cable TV network is bi-directional. The network is connected if there is at least one interconnection path between each pair of relays present in the network. Otherwise the network is disconnected. An empty network or a network with a single relay is considered connected. The safety factor f of a network with n relays is:
1. n, if the net remains connected regardless the number of relays removed from the net.
2. The minimal number of relays that disconnect the network when removed.
For example, consider the nets from figure 1, where the circles mark the relays and the solid lines correspond to interconnection cables. The network (a) is connected regardless the number of relays that are removed and, according to rule (1), f=n=3. The network (b) is disconnected when 0 relays are removed, hence f=0 by rule (2). The network (c) is disconnected when the relays 1 and 2 or 1 and 3 are removed. The safety factor is 2.

Input

Write a program that reads several data sets from the standard input and computes the safety factor for the cable networks encoded by the data sets. Each data set starts with two integers: 0<=n<=50,the number of relays in the net, and m, the number of cables in the net. Follow m data pairs (u,v), u < v, where u and v are relay identifiers (integers in the range 0..n-1). The pair (u,v) designates the cable that interconnects the relays u and v. The pairs may occur in any order.Except the (u,v) pairs, which do not contain white spaces, white spaces can occur freely in input. Input data terminate with an end of file and are correct.

Output

For each data set, the program prints on the standard output, from the beginning of a line, the safety factor of the encoded net.

Sample Input

0 0
1 0
3 3 (0,1) (0,2) (1,2)
2 0
5 7 (0,1) (0,2) (1,3) (1,2) (1,4) (2,3) (3,4)

Sample Output

Hint

The first data set encodes an empty network, the second data set corresponds to a network with a single relay, and the following three data sets encode the nets shown in figure 1.

Source

Southeastern Europe 2004

题目类型：顶点连通度(最小割)

算法分析：使用独立轨和Menger定理将求解顶点连通度的问题转化成求解最小割的问题，对于任意两点a、b之间的最大独立轨数目的求解可以使用网络流。建图方式为先将点i拆点为i’和i”，然后构造<i’, i”>，容量为1。对于原图中的<u, v>，构造<u”, v’>和<v”, u’>，容量为INF。最后枚举源点s”和汇点e’，计算最大流并更新res。若res == INF，则表示顶点连通度为n，否则为res。注意枚举源点和汇点时两个点不能相邻！！！

/*************************************************
Author        :supermaker
Created Time  :2016/4/9 13:00:09
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 4e4 + 66;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 200 + 66;

struct Node
{
	int v, nxt, c, f;	
};

Node edge[maxn*maxn];
int head[maxn], edgelen;
int dep[maxn], cnt[maxn], cur[maxn];

void Init ()
{
	memset (head, -1, sizeof (head));
	memset (edge, -1, sizeof (edge));
	edgelen = 0;
}

void AddEdge (int u, int v, int w, int rw = 0)
{
	edge[edgelen].v = v, edge[edgelen].c = w, edge[edgelen].f = 0;
	edge[edgelen].nxt = head[u], head[u] = edgelen++;
	edge[edgelen].v = u, edge[edgelen].c = rw, edge[edgelen].f = 0;
	edge[edgelen].nxt = head[v], head[v] = edgelen++;
}

void bfs (int s, int e)
{
	memset (dep, -1, sizeof (dep));
	memset (cnt, 0, sizeof (cnt));
	dep[e] = 0;
	cnt[dep[e]]++;
	queue <int> qu;
	qu.push (e);
	while (!qu.empty ())
	{
		int u = qu.front (); qu.pop ();
		for (int i = head[u]; i != -1; i = edge[i].nxt)
		{
			int v = edge[i].v;
			if (dep[v] != -1) continue;
			qu.push (v);
			dep[v] = dep[u] + 1;
			cnt[dep[v]]++;
		}
	}
}

int sta[maxn];
int MaxFlow (int s, int e, int n)
{
	bfs (s, e);
	int res = 0, top = 0, u = s;
	memcpy (cur, head, sizeof (head));
	while (dep[s] < n)
	{
		if (u == e)
		{
			int minval = INF, minval_pos = -1;
			for (int i = 0; i < top; i++)
				if (minval > edge[sta[i]].c - edge[sta[i]].f)
				{
					minval = edge[sta[i]].c - edge[sta[i]].f;
					minval_pos = i;
				}
			for (int i = 0; i < top; i++)
			{
				edge[sta[i]].f += minval;
				edge[sta[i]^1].f -= minval;
			}
			res += minval;
			top = minval_pos;
			u = edge[sta[top]^1].v;
		}
		else
		{
			bool is_have = false;
			for (int i = cur[u]; i != -1; i = edge[i].nxt)
			{
				int v = edge[i].v;
				if (edge[i].c - edge[i].f && dep[v] + 1 == dep[u])
				{
					cur[u] = i;
					sta[top++] = cur[u];
					u = v;
					is_have = true;
					break;
				}
			}
			if (is_have) continue;
			int minval = n;
			for (int i = head[u]; i != -1; i = edge[i].nxt)
				if (edge[i].c - edge[i].f && dep[edge[i].v] < minval)
				{
					minval = dep[edge[i].v];
					cur[u] = i;
				}
			cnt[dep[u]]--;
			if (!cnt[dep[u]]) return res;
			dep[u] = minval + 1;
			cnt[dep[u]]++;
			if (u != s) u = edge[sta[--top]^1].v;
		}
	}
	return res;
}

int n, m;
bool g[maxn][maxn];

void Build ()
{
	Init ();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
				AddEdge (i, n + i, 1);
			else if (g[i][j])
				AddEdge (n + i, j, INF);
		}
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		memset (g, false, sizeof (g));
		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf (" (%d,%d) ", &u, &v);
			u++, v++;
			g[u][v] = g[v][u] = true;
		}

		int res = INF;
		for (int i = 1; i <= n; i++)
			for (int j = i + 1; j <= n; j++)
			{
				if (!g[i][j])
				{
					Build ();	
					int tt = MaxFlow (n + i, j, 2 * n);
					res = min (res, tt);
				}
			}
		if (res >= INF) printf ("%d\n", n);
		else printf ("%d\n", res);
	}
    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

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

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

/*************************************************

Author :supermaker

Created Time :2016/4/9 13:00:09

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 4e4 + 66;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 200 + 66;

struct Node

{

int v, nxt, c, f;

};

Node edge[maxn*maxn];

int head[maxn], edgelen;

int dep[maxn], cnt[maxn], cur[maxn];

void Init ()

{

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

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

edgelen = 0;

}

void AddEdge (int u, int v, int w, int rw = 0)

{

edge[edgelen].v = v, edge[edgelen].c = w, edge[edgelen].f = 0;

edge[edgelen].nxt = head[u], head[u] = edgelen++;

edge[edgelen].v = u, edge[edgelen].c = rw, edge[edgelen].f = 0;

edge[edgelen].nxt = head[v], head[v] = edgelen++;

}

void bfs (int s, int e)

{

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

memset (cnt, 0, sizeof (cnt));

dep[e] = 0;

cnt[dep[e]]++;

queue <int> qu;

qu.push (e);

while (!qu.empty ())

{

int u = qu.front (); qu.pop ();

for (int i = head[u]; i != -1; i = edge[i].nxt)

{

int v = edge[i].v;

if (dep[v] != -1) continue;

qu.push (v);

dep[v] = dep[u] + 1;

cnt[dep[v]]++;

}

int sta[maxn];

int MaxFlow (int s, int e, int n)

{

bfs (s, e);

int res = 0, top = 0, u = s;

memcpy (cur, head, sizeof (head));

while (dep[s] < n)

{

if (u == e)

{

int minval = INF, minval_pos = -1;

for (int i = 0; i < top; i++)

if (minval > edge[sta[i]].c - edge[sta[i]].f)

{

minval = edge[sta[i]].c - edge[sta[i]].f;

minval_pos = i;

}

for (int i = 0; i < top; i++)

{

edge[sta[i]].f += minval;

edge[sta[i]^1].f -= minval;

}

res += minval;

top = minval_pos;

u = edge[sta[top]^1].v;

}

else

{

bool is_have = false;

for (int i = cur[u]; i != -1; i = edge[i].nxt)

{

int v = edge[i].v;

if (edge[i].c - edge[i].f && dep[v] + 1 == dep[u])

{

cur[u] = i;

sta[top++] = cur[u];

u = v;

is_have = true;

break;

}

if (is_have) continue;

int minval = n;

for (int i = head[u]; i != -1; i = edge[i].nxt)

if (edge[i].c - edge[i].f && dep[edge[i].v] < minval)

{

minval = dep[edge[i].v];

cur[u] = i;

}

cnt[dep[u]]--;

if (!cnt[dep[u]]) return res;

dep[u] = minval + 1;

cnt[dep[u]]++;

if (u != s) u = edge[sta[--top]^1].v;

}

return res;

}

int n, m;

bool g[maxn][maxn];

void Build ()

{

Init ();

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

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

{

if (i == j)

AddEdge (i, n + i, 1);

else if (g[i][j])

AddEdge (n + i, j, INF);

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &n, &m) != EOF)

{

memset (g, false, sizeof (g));

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

{

int u, v;

scanf (" (%d,%d) ", &u, &v);

u++, v++;

g[u][v] = g[v][u] = true;

}

int res = INF;

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

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

{

if (!g[i][j])

{

Build ();

int tt = MaxFlow (n + i, j, 2 * n);

res = min (res, tt);

}

if (res >= INF) printf ("%d\n", n);

else printf ("%d\n", res);

}

return 0;

}

poj2125

maksyuki 发表于 oj 分类，标签: 图论(网络流)-最大流, 图论(网络流)-最小割, 图论-最小点权覆盖

07 4月 2016

Destroying The Graph

Alice and Bob play the following game. First, Alice draws some directed graph with N vertices and M arcs. After that Bob tries to destroy it. In a move he may take any vertex of the graph and remove either all arcs incoming into this vertex, or all arcs outgoing from this vertex.
Alice assigns two costs to each vertex: Wi⁺ and Wi^-. If Bob removes all arcs incoming into the i-th vertex he pays Wi⁺ dollars to Alice, and if he removes outgoing arcs he pays Wi^- dollars.
Find out what minimal sum Bob needs to remove all arcs from the graph.

Input

Input file describes the graph Alice has drawn. The first line of the input file contains N and M (1 <= N <= 100, 1 <= M <= 5000). The second line contains N integer numbers specifying Wi⁺. The third line defines Wi^- in a similar way. All costs are positive and do not exceed 10⁶ . Each of the following M lines contains two integers describing the corresponding arc of the graph. Graph may contain loops and parallel arcs.

Output

On the first line of the output file print W --- the minimal sum Bob must have to remove all arcs from the graph. On the second line print K --- the number of moves Bob needs to do it. After that print K lines that describe Bob's moves. Each line must first contain the number of the vertex and then '+' or '-' character, separated by one space. Character '+' means that Bob removes all arcs incoming into the specified vertex and '-' that Bob removes all arcs outgoing from the specified vertex.

Sample Input

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

Sample Output

1 +

2 -

2 +

Source

Northeastern Europe 2003, Northern Subregion

题目类型：最小点权覆盖(最小割)

算法分析：每个点都有两个属性(删除入边的权值和删除出边的权值)，则拆点一个处理入边，一个处理出边，使得原图转化为二分图。对于给出的边<u, v>，从u向n+v连一条容量为INF的有向边，从源点向点1~n分别连一条容量为对应点出边点权的有向边，从点n~2n分别向汇点连一条容量为对应点入边点权的有向边。最后跑一个最大流就可得到最小费用值。最后从源点s开始dfs将在残余网络中在同一个连通分量中的点打上标记，所有1~n中没有标记的点就是选择删除出边的，n~2n中被标记的点就是选择删除入边的

/*************************************************
Author        :supermaker
Created Time  :2016/4/7 21:19:29
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

struct Node
{
	int v, nxt, c, f;	
};

Node edge[maxn*maxn];
int head[maxn], edgelen;
int dep[maxn], cnt[maxn], cur[maxn];

void Init ()
{
	memset (head, -1, sizeof (head));
	memset (edge, -1, sizeof (edge));
	edgelen = 0;
}

void AddEdge (int u, int v, int w, int rw = 0)
{
	edge[edgelen].v = v, edge[edgelen].c = w, edge[edgelen].f = 0;
	edge[edgelen].nxt = head[u], head[u] = edgelen++;
	edge[edgelen].v = u, edge[edgelen].c = rw, edge[edgelen].f = 0;
	edge[edgelen].nxt = head[v], head[v] = edgelen++;
}

void bfs (int s, int e)
{
	memset (dep, -1, sizeof (dep));
	memset (cnt, 0, sizeof (cnt));
	dep[e] = 0;
	cnt[dep[e]]++;
	queue <int> qu;
	qu.push (e);
	while (!qu.empty ())
	{
		int u = qu.front (); qu.pop ();
		for (int i = head[u]; i != -1; i = edge[i].nxt)
		{
			int v = edge[i].v;
			if (dep[v] != -1) continue;
			qu.push (v);
			dep[v] = dep[u] + 1;
			cnt[dep[v]]++;
		}
	}
}

int sta[maxn];
int MaxFlow (int s, int e, int n)
{
	bfs (s, e);
	int res = 0, top = 0, u = s;
	memcpy (cur, head, sizeof (head));
	while (dep[s] < n)
	{
		if (u == e)
		{
			int minval = INF, minval_pos = -1;
			for (int i = 0; i < top; i++)
				if (minval > edge[sta[i]].c - edge[sta[i]].f)
				{
					minval = edge[sta[i]].c - edge[sta[i]].f;
					minval_pos = i;
				}
			for (int i = 0; i < top; i++)
			{
				edge[sta[i]].f += minval;
				edge[sta[i]^1].f -= minval;
			}
			res += minval;
			top = minval_pos;
			u = edge[sta[top]^1].v;
		}
		else
		{
			bool is_have = false;
			for (int i = cur[u]; i != -1; i = edge[i].nxt)
			{
				int v = edge[i].v;
				if (edge[i].c - edge[i].f && dep[v] + 1 == dep[u])
				{
					cur[u] = i;
					sta[top++] = cur[u];
					u = v;
					is_have = true;
					break;
				}
			}
			if (is_have) continue;
			int minval = n;
			for (int i = head[u]; i != -1; i = edge[i].nxt)
				if (edge[i].c - edge[i].f && dep[edge[i].v] < minval)
				{
					minval = dep[edge[i].v];
					cur[u] = i;
				}
			cnt[dep[u]]--;
			if (!cnt[dep[u]]) return res;
			dep[u] = minval + 1;
			cnt[dep[u]]++;
			if (u != s) u = edge[sta[--top]^1].v;
		}
	}
	return res;
}

int in[maxn], out[maxn];
bool vis[maxn];

void dfs (int u)
{
	vis[u] = true;
	for (int i = head[u]; i != -1; i = edge[i].nxt)
	{
		int v = edge[i].v;
		if (edge[i].c - edge[i].f && !vis[v])
			dfs (v);
	}
}

int main()
{
    //CFF;
    //CPPFF;
	int n, m;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		for (int i = 1; i <= n; i++)
			scanf ("%d", &in[i]);
		for (int i = 1; i <= n; i++)
			scanf ("%d", &out[i]);

		Init ();
		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			AddEdge (u, n + v, INF);
		}
		for (int i = 1; i <= n; i++)
			AddEdge (0, i, out[i]);
		for (int i = 1; i <= n; i++)
			AddEdge (n + i, 2 * n + 1, in[i]);

		printf ("%d\n", MaxFlow (0, 2 * n + 1, 2 * n + 2));
		memset (vis, false, sizeof (vis));
		dfs (0);
		int tot = 0;
		for (int i = 1; i <= n; i++)
		{
			if (!vis[i]) tot++;
			if (vis[n+i]) tot++;
		}
		printf ("%d\n", tot);
		for (int i = 1; i <= n; i++)
		{
			if (!vis[i]) printf ("%d -\n", i);
			if (vis[n+i]) printf ("%d +\n", i);
		}
	}
    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

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

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

/*************************************************

Author :supermaker

Created Time :2016/4/7 21:19:29

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 200 + 66;

struct Node

{

int v, nxt, c, f;

};

Node edge[maxn*maxn];

int head[maxn], edgelen;

int dep[maxn], cnt[maxn], cur[maxn];

void Init ()

{

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

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

edgelen = 0;

}

void AddEdge (int u, int v, int w, int rw = 0)

{

edge[edgelen].v = v, edge[edgelen].c = w, edge[edgelen].f = 0;

edge[edgelen].nxt = head[u], head[u] = edgelen++;

edge[edgelen].v = u, edge[edgelen].c = rw, edge[edgelen].f = 0;

edge[edgelen].nxt = head[v], head[v] = edgelen++;

}

void bfs (int s, int e)

{

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

memset (cnt, 0, sizeof (cnt));

dep[e] = 0;

cnt[dep[e]]++;

queue <int> qu;

qu.push (e);

while (!qu.empty ())

{

int u = qu.front (); qu.pop ();

for (int i = head[u]; i != -1; i = edge[i].nxt)

{

int v = edge[i].v;

if (dep[v] != -1) continue;

qu.push (v);

dep[v] = dep[u] + 1;

cnt[dep[v]]++;

}

int sta[maxn];

int MaxFlow (int s, int e, int n)

{

bfs (s, e);

int res = 0, top = 0, u = s;

memcpy (cur, head, sizeof (head));

while (dep[s] < n)

{

if (u == e)

{

int minval = INF, minval_pos = -1;

for (int i = 0; i < top; i++)

if (minval > edge[sta[i]].c - edge[sta[i]].f)

{

minval = edge[sta[i]].c - edge[sta[i]].f;

minval_pos = i;

}

for (int i = 0; i < top; i++)

{

edge[sta[i]].f += minval;

edge[sta[i]^1].f -= minval;

}

res += minval;

top = minval_pos;

u = edge[sta[top]^1].v;

}

else

{

bool is_have = false;

for (int i = cur[u]; i != -1; i = edge[i].nxt)

{

int v = edge[i].v;

if (edge[i].c - edge[i].f && dep[v] + 1 == dep[u])

{

cur[u] = i;

sta[top++] = cur[u];

u = v;

is_have = true;

break;

}

if (is_have) continue;

int minval = n;

for (int i = head[u]; i != -1; i = edge[i].nxt)

if (edge[i].c - edge[i].f && dep[edge[i].v] < minval)

{

minval = dep[edge[i].v];

cur[u] = i;

}

cnt[dep[u]]--;

if (!cnt[dep[u]]) return res;

dep[u] = minval + 1;

cnt[dep[u]]++;

if (u != s) u = edge[sta[--top]^1].v;

}

return res;

}

int in[maxn], out[maxn];

bool vis[maxn];

void dfs (int u)

{

vis[u] = true;

for (int i = head[u]; i != -1; i = edge[i].nxt)

{

int v = edge[i].v;

if (edge[i].c - edge[i].f && !vis[v])

dfs (v);

}

int main()

{

//CFF;

//CPPFF;

int n, m;

while (scanf ("%d%d", &n, &m) != EOF)

{

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

scanf ("%d", &in[i]);

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

scanf ("%d", &out[i]);

Init ();

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

{

int u, v;

scanf ("%d%d", &u, &v);

AddEdge (u, n + v, INF);

}

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

AddEdge (0, i, out[i]);

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

AddEdge (n + i, 2 * n + 1, in[i]);

printf ("%d\n", MaxFlow (0, 2 * n + 1, 2 * n + 2));

memset (vis, false, sizeof (vis));

dfs (0);

int tot = 0;

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

{

if (!vis[i]) tot++;

if (vis[n+i]) tot++;

}

printf ("%d\n", tot);

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

{

if (!vis[i]) printf ("%d -\n", i);

if (vis[n+i]) printf ("%d +\n", i);

}

return 0;

}

poj2175

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

07 4月 2016

Evacuation Plan

The City has a number of municipal buildings and a number of fallout shelters that were build specially to hide municipal workers in case of a nuclear war. Each fallout shelter has a limited capacity in terms of a number of people it can accommodate, and there's almost no excess capacity in The City's fallout shelters. Ideally, all workers from a given municipal building shall run to the nearest fallout shelter. However, this will lead to overcrowding of some fallout shelters, while others will be half-empty at the same time.

To address this problem, The City Council has developed a special evacuation plan. Instead of assigning every worker to a fallout shelter individually (which will be a huge amount of information to keep), they allocated fallout shelters to municipal buildings, listing the number of workers from every building that shall use a given fallout shelter, and left the task of individual assignments to the buildings' management. The plan takes into account a number of workers in every building - all of them are assigned to fallout shelters, and a limited capacity of each fallout shelter - every fallout shelter is assigned to no more workers then it can accommodate, though some fallout shelters may be not used completely.

The City Council claims that their evacuation plan is optimal, in the sense that it minimizes the total time to reach fallout shelters for all workers in The City, which is the sum for all workers of the time to go from the worker's municipal building to the fallout shelter assigned to this worker.

The City Mayor, well known for his constant confrontation with The City Council, does not buy their claim and hires you as an independent consultant to verify the evacuation plan. Your task is to either ensure that the evacuation plan is indeed optimal, or to prove otherwise by presenting another evacuation plan with the smaller total time to reach fallout shelters, thus clearly exposing The City Council's incompetence.

During initial requirements gathering phase of your project, you have found that The City is represented by a rectangular grid. The location of municipal buildings and fallout shelters is specified by two integer numbers and the time to go between municipal building at the location (Xi, Yi) and the fallout shelter at the location (Pj, Qj) is D_i,j = |Xi - Pj| + |Yi - Qj| + 1 minutes.

Input

The input consists of The City description and the evacuation plan description. The first line of the input file consists of two numbers N and M separated by a space. N (1 ≤ N ≤ 100) is a number of municipal buildings in The City (all municipal buildings are numbered from 1 to N). M (1 ≤ M ≤ 100) is a number of fallout shelters in The City (all fallout shelters are numbered from 1 to M).

The following N lines describe municipal buildings. Each line contains there integer numbers Xi, Yi, and Bi separated by spaces, where Xi, Yi (-1000 ≤ Xi, Yi ≤ 1000) are the coordinates of the building, and Bi (1 ≤ Bi ≤ 1000) is the number of workers in this building.

The description of municipal buildings is followed by M lines that describe fallout shelters. Each line contains three integer numbers Pj, Qj, and Cj separated by spaces, where Pi, Qi (-1000 ≤ Pj, Qj ≤ 1000) are the coordinates of the fallout shelter, and Cj (1 ≤ Cj ≤ 1000) is the capacity of this shelter.

The description of The City Council's evacuation plan follows on the next N lines. Each line represents an evacuation plan for a single building (in the order they are given in The City description). The evacuation plan of ith municipal building consists of M integer numbers E_i,j separated by spaces. E_i,j (0 ≤ E_i,j ≤ 1000) is a number of workers that shall evacuate from the i^th municipal building to the j^th fallout shelter.

The plan in the input file is guaranteed to be valid. Namely, it calls for an evacuation of the exact number of workers that are actually working in any given municipal building according to The City description and does not exceed the capacity of any given fallout shelter.

Output

If The City Council's plan is optimal, then write to the output the single word OPTIMAL. Otherwise, write the word SUBOPTIMAL on the first line, followed by N lines that describe your plan in the same format as in the input file. Your plan need not be optimal itself, but must be valid and better than The City Council's one.

Sample Input

3 4
-3 3 5
-2 -2 6
2 2 5
-1 1 3
1 1 4
-2 -2 7
0 -1 3
3 1 1 0
0 0 6 0
0 3 0 2

Sample Output

SUBOPTIMAL

3 0 1 1

0 0 6 0

0 4 0 1

Source

Northeastern Europe 2002

题目类型：最小费用流(消圈)

算法分析：直接使用最小费用流算法得到的结果是正确的而且是最优方案，但是会TLE。由于本题没有要求最后求得的最终方案一定是最优的，这里使用费用流的消圈算法来求解。消圈定理描述为残余网络里若存在负费用圈，那么当前流不是最小费用流。负圈指的是费用总和为负且每条边剩余流量大于零的圈。若能够在原图中找到一个费用为负的圈的话，那么沿着这个圈流量增加1就能够在不改变原始总流量的基础上使得总费用变得更低，所以只要找到一个负圈即可，先按照输入构造残余网络，然后利用SPFA判断是否存在负圈，若存在负圈则沿着负圈上的点相应修改流量

/*************************************************
Author        :supermaker
Created Time  :2016/4/6 19:04:05
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

struct Node
{
	int v, nxt, c, f, cost; 	
};

struct Point
{
	int x, y, v;	
};

Point aa[maxn], bb[maxn];
Node edge[maxn*maxn];
int head[maxn], edgelen;
int allrow[maxn], allcol[maxn], cap[maxn][maxn];

int Dis (int i, int j)
{
	return abs (aa[i].x - bb[j].x) + abs (aa[i].y - bb[j].y) + 1;
}

void Init ()
{
	memset (head, -1, sizeof (head));
	memset (edge, -1, sizeof (edge));
	edgelen = 0;
}

void AddEdge (int cost, int u, int v, int w, int rw = 0)
{
	edge[edgelen].v = v, edge[edgelen].c = w, edge[edgelen].f = 0;
	edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++;
	edge[edgelen].v = u, edge[edgelen].c = rw, edge[edgelen].f = 0;
	edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++;
}

int dis[maxn], cnt[maxn], inq[maxn], par[maxn];
int N, rt = -1;

bool spfa (int s)
{
	for (int i = 0; i <= N; i++)
	{
		dis[i] = INF;
		inq[i] = cnt[i] = 0;
		par[i] = -1;
	}
	dis[s] = 0;
	queue <int> qu;
	qu.push (s);
	inq[s]++, cnt[s]++;
	while (!qu.empty ())
	{
		int u = qu.front (); qu.pop (); inq[u]--;
		if (cnt[u] > N)
		{
			rt = u;
			return false;
		}

		for (int i = head[u]; i != -1; i = edge[i].nxt)
		{
			int v = edge[i].v;
			if (edge[i].c && dis[u] < INF && dis[v] > dis[u] + edge[i].cost)
			{
				dis[v] = dis[u] + edge[i].cost;
				par[v] = u;
				if (!inq[v])
				{
					qu.push (v);
					inq[v]++, cnt[v]++;
				}
			}
		}
	}
	return true;
}

int n, m;
void SS (int s)
{
	if (spfa (s))
		puts ("OPTIMAL");
	else
	{
		puts ("SUBOPTIMAL");
		int sta = rt;
		memset (inq, 0, sizeof (inq));
		while (1)
		{
			if (!inq[sta]) 
			{
				inq[sta]++, sta = par[sta];
			}
			else
			{
				rt = sta;
				break;
			}
		}
		do
		{
			int u = par[sta], v = sta;
			if (u <= n && v > n) cap[u][v-n]++;
			if (v <= n && u > n) cap[v][u-n]--;
			sta = par[sta];
		} while (sta != rt);

		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				if (j == 1) printf ("%d", cap[i][j]);
				else printf (" %d", cap[i][j]);
			}
			puts ("");
		}
	}
}


int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		for (int i = 1; i <= n; i++)
			scanf ("%d%d%d", &aa[i].x, &aa[i].y, &aa[i].v);

		for (int i = 1; i <= m; i++) 
			scanf ("%d%d%d", &bb[i].x, &bb[i].y, &bb[i].v);
		
		Init ();
		memset (allrow, 0, sizeof (allrow));
		memset (allcol, 0, sizeof (allcol));
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				scanf ("%d", &cap[i][j]);
				allrow[i] += cap[i][j];
				allcol[j] += cap[i][j]; 
				AddEdge (Dis (i, j), i, n + j, INF - cap[i][j], cap[i][j]);
			}
		
		for (int i = 1; i <= n; i++)
			AddEdge (0, 0, i, aa[i].v - allrow[i], allrow[i]);

		for (int i = 1; i <= m; i++)
			AddEdge (0, n + i, n + m + 1, bb[i].v - allcol[i], allcol[i]);

		N = n + m + 2;
		SS (N - 1);
	}
    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

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

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

/*************************************************

Author :supermaker

Created Time :2016/4/6 19:04:05

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 200 + 66;

struct Node

{

int v, nxt, c, f, cost;

};

struct Point

{

int x, y, v;

};

Point aa[maxn], bb[maxn];

Node edge[maxn*maxn];

int head[maxn], edgelen;

int allrow[maxn], allcol[maxn], cap[maxn][maxn];

int Dis (int i, int j)

{

return abs (aa[i].x - bb[j].x) + abs (aa[i].y - bb[j].y) + 1;

}

void Init ()

{

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

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

edgelen = 0;

}

void AddEdge (int cost, int u, int v, int w, int rw = 0)

{

edge[edgelen].v = v, edge[edgelen].c = w, edge[edgelen].f = 0;

edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++;

edge[edgelen].v = u, edge[edgelen].c = rw, edge[edgelen].f = 0;

edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++;

}

int dis[maxn], cnt[maxn], inq[maxn], par[maxn];

int N, rt = -1;

bool spfa (int s)

{

for (int i = 0; i <= N; i++)

{

dis[i] = INF;

inq[i] = cnt[i] = 0;

par[i] = -1;

}

dis[s] = 0;

queue <int> qu;

qu.push (s);

inq[s]++, cnt[s]++;

while (!qu.empty ())

{

int u = qu.front (); qu.pop (); inq[u]--;

if (cnt[u] > N)

{

rt = u;

return false;

}

for (int i = head[u]; i != -1; i = edge[i].nxt)

{

int v = edge[i].v;

if (edge[i].c && dis[u] < INF && dis[v] > dis[u] + edge[i].cost)

{

dis[v] = dis[u] + edge[i].cost;

par[v] = u;

if (!inq[v])

{

qu.push (v);

inq[v]++, cnt[v]++;

}

return true;

}

int n, m;

void SS (int s)

{

if (spfa (s))

puts ("OPTIMAL");

else

{

puts ("SUBOPTIMAL");

int sta = rt;

memset (inq, 0, sizeof (inq));

while (1)

{

if (!inq[sta])

{

inq[sta]++, sta = par[sta];

}

else

{

rt = sta;

break;

}

{

int u = par[sta], v = sta;

if (u <= n && v > n) cap[u][v-n]++;

if (v <= n && u > n) cap[v][u-n]--;

sta = par[sta];

} while (sta != rt);

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

{

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

{

if (j == 1) printf ("%d", cap[i][j]);

else printf (" %d", cap[i][j]);

}

puts ("");

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &n, &m) != EOF)

{

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

scanf ("%d%d%d", &aa[i].x, &aa[i].y, &aa[i].v);

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

scanf ("%d%d%d", &bb[i].x, &bb[i].y, &bb[i].v);

Init ();

memset (allrow, 0, sizeof (allrow));

memset (allcol, 0, sizeof (allcol));

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

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

{

scanf ("%d", &cap[i][j]);

allrow[i] += cap[i][j];

allcol[j] += cap[i][j];

AddEdge (Dis (i, j), i, n + j, INF - cap[i][j], cap[i][j]);

}

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

AddEdge (0, 0, i, aa[i].v - allrow[i], allrow[i]);

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

AddEdge (0, n + i, n + m + 1, bb[i].v - allcol[i], allcol[i]);

N = n + m + 2;

SS (N - 1);

}

return 0;

}

poj2516

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

05 4月 2016

Minimum Cost

Dearboy, a goods victualer, now comes to a big problem, and he needs your help. In his sale area there are N shopkeepers (marked from 1 to N) which stocks goods from him.Dearboy has M supply places (marked from 1 to M), each provides K different kinds of goods (marked from 1 to K). Once shopkeepers order goods, Dearboy should arrange which supply place provide how much amount of goods to shopkeepers to cut down the total cost of transport.

It's known that the cost to transport one unit goods for different kinds from different supply places to different shopkeepers may be different. Given each supply places' storage of K kinds of goods, N shopkeepers' order of K kinds of goods and the cost to transport goods for different kinds from different supply places to different shopkeepers, you should tell how to arrange the goods supply to minimize the total cost of transport.

Input

The input consists of multiple test cases. The first line of each test case contains three integers N, M, K (0 < N, M, K < 50), which are described above. The next N lines give the shopkeepers' orders, with each line containing K integers (there integers are belong to [0, 3]), which represents the amount of goods each shopkeeper needs. The next M lines give the supply places' storage, with each line containing K integers (there integers are also belong to [0, 3]), which represents the amount of goods stored in that supply place.

Then come K integer matrices (each with the size N * M), the integer (this integer is belong to (0, 100)) at the i-th row, j-th column in the k-th matrix represents the cost to transport one unit of k-th goods from the j-th supply place to the i-th shopkeeper.

The input is terminated with three "0"s. This test case should not be processed.

Output

For each test case, if Dearboy can satisfy all the needs of all the shopkeepers, print in one line an integer, which is the minimum cost; otherwise just output "-1".

Sample Input

1 3 3
1 1 1
0 1 1
1 2 2
1 0 1
1 2 3
1 1 1
2 1 1

1 1 1
3
2
20

0 0 0

Sample Output

-1

Source

POJ Monthly--2005.07.31, Wang Yijie

题目类型：最小费用最大流

算法分析：首先将每个物品需求量和供给量读入并判断，若供不应求则输出-1。否则对于每个物品ki，跑一个最小费用流，建图方式为：从源点s向每个供应商连一条容量为当前供应商ki供应量，花费为0的有向边，从每个店主向汇点e连一条容量为当前店主ki需求量，花费为0的有向边。对于每个给出的从供应商到店主的关系，连一条容量为INF，花费为所给花费的有向边。最后将每次费用流得到的花费累加即可。注意不拆开建图会TLE！！！

/*************************************************
Author        :supermaker
Created Time  :2016/4/4 21:18:22
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

struct Node
{
	int to, nxt, c, f, cost;
};

Node edge[maxn*66];
int head[maxn], edgelen;

void Init ()
{
	memset (head, -1, sizeof (head));
	memset (edge, -1, sizeof (edge));
	edgelen = 0;
}

void AddEdge (int cost, int u, int v, int w, int rw = 0)
{
	edge[edgelen].to = v, edge[edgelen].c = w, edge[edgelen].f = 0;
	edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++;
	edge[edgelen].to = u, edge[edgelen].c = rw, edge[edgelen].f = 0;
	edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++;
}

int dis[maxn], cnt[maxn], inq[maxn], par[maxn];
int N;

bool spfa (int s, int e)
{
	for (int i = 0; i <= N; i++)
	{
		dis[i] = INF;
		inq[i] = cnt[i] = 0;
		par[i] = -1;
	}
	dis[s] = 0;
	queue <int> qu;
	qu.push (s);
	inq[s]++, cnt[s]++;
	while (!qu.empty ())
	{
		int u = qu.front (); qu.pop (); inq[u]--;
		if (cnt[u] > N) return false;
		for (int i = head[u]; i != -1; i = edge[i].nxt)
		{
			int v = edge[i].to;
			if (edge[i].c - edge[i].f && dis[u] < INF && dis[v] > dis[u] + edge[i].cost)
			{
				dis[v] = dis[u] + edge[i].cost;
				par[v] = i;
				if (!inq[v])
				{
					qu.push (v);
					inq[v]++, cnt[v]++;
				}
			}
		}
	}
	if (par[e] == -1) return false;
	return true;
}

int allcost;
int MinCostMaxFlow (int s, int e)
{
	int res = 0;
	allcost = 0;
	while (spfa (s, e))
	{
		int minval = INF;
		for (int i = par[e]; i != -1; i = par[edge[i^1].to])
			minval = min (minval, edge[i].c - edge[i].f);
		for (int i = par[e]; i != -1; i = par[edge[i^1].to])
		{
			edge[i].f += minval;
			edge[i^1].f -= minval;
			allcost += edge[i].cost * minval;
		}
		res += minval;
	}
	return res;
}

int aa[66][66], bb[66][66];
int numsup[66], numneed[66];

int main()
{
    //CFF;
    //CPPFF;
	int num, M, K;
	while (scanf ("%d%d%d", &num, &M, &K) != EOF)
	{
		if (num == 0 && M == 0 && K == 0) break;

		memset (numsup, 0, sizeof (numsup));
		memset (numneed, 0, sizeof (numneed));
		for (int i = 1; i <= num; i++)
			for (int j = 1; j <= K; j++)
			{
				scanf ("%d", &aa[i][j]);
				numneed[j] += aa[i][j];
			}

		for (int i = 1; i <= M; i++)
			for (int j = 1; j <= K; j++)
			{
				scanf ("%d", &bb[i][j]);
				numsup[j] += bb[i][j];	
			}
		
		bool is_valid = true;
		for (int i = 1; i <= K; i++)
			if (numneed[i] > numsup[i])
			{
				is_valid = false;
				break;
			}

		int ans = 0;
		for (int k = 1; k <= K; k++)
		{
			Init ();
			int val;
			for (int i = 1; i <= num; i++)
				for (int j = 1; j <= M; j++)
				{
					scanf ("%d", &val);
					AddEdge (val, num + j, i, INF);
				}
			N = num + M + 2;
			for (int i = 1; i <= M; i++)
				AddEdge (0, 0, num + i, bb[i][k]);

			for (int i = 1; i <= num; i++)
				AddEdge (0, i, N - 1, aa[i][k]);
		
			MinCostMaxFlow (0, N - 1);
			ans += allcost;
		}

		if (!is_valid)
			puts ("-1");
		else
			printf ("%d\n", ans);
	}
    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

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

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

/*************************************************

Author :supermaker

Created Time :2016/4/4 21:18:22

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 5000 + 66;

struct Node

{

int to, nxt, c, f, cost;

};

Node edge[maxn*66];

int head[maxn], edgelen;

void Init ()

{

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

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

edgelen = 0;

}

void AddEdge (int cost, int u, int v, int w, int rw = 0)

{

edge[edgelen].to = v, edge[edgelen].c = w, edge[edgelen].f = 0;

edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++;

edge[edgelen].to = u, edge[edgelen].c = rw, edge[edgelen].f = 0;

edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++;

}

int dis[maxn], cnt[maxn], inq[maxn], par[maxn];

int N;

bool spfa (int s, int e)

{

for (int i = 0; i <= N; i++)

{

dis[i] = INF;

inq[i] = cnt[i] = 0;

par[i] = -1;

}

dis[s] = 0;

queue <int> qu;

qu.push (s);

inq[s]++, cnt[s]++;

while (!qu.empty ())

{

int u = qu.front (); qu.pop (); inq[u]--;

if (cnt[u] > N) return false;

for (int i = head[u]; i != -1; i = edge[i].nxt)

{

int v = edge[i].to;

if (edge[i].c - edge[i].f && dis[u] < INF && dis[v] > dis[u] + edge[i].cost)

{

dis[v] = dis[u] + edge[i].cost;

par[v] = i;

if (!inq[v])

{

qu.push (v);

inq[v]++, cnt[v]++;

}

if (par[e] == -1) return false;

return true;

}

int allcost;

int MinCostMaxFlow (int s, int e)

{

int res = 0;

allcost = 0;

while (spfa (s, e))

{

int minval = INF;

for (int i = par[e]; i != -1; i = par[edge[i^1].to])

minval = min (minval, edge[i].c - edge[i].f);

for (int i = par[e]; i != -1; i = par[edge[i^1].to])

{

edge[i].f += minval;

edge[i^1].f -= minval;

allcost += edge[i].cost * minval;

}

res += minval;

}

return res;

}

int aa[66][66], bb[66][66];

int numsup[66], numneed[66];

int main()

{

//CFF;

//CPPFF;

int num, M, K;

while (scanf ("%d%d%d", &num, &M, &K) != EOF)

{

if (num == 0 && M == 0 && K == 0) break;

memset (numsup, 0, sizeof (numsup));

memset (numneed, 0, sizeof (numneed));

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

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

{

scanf ("%d", &aa[i][j]);

numneed[j] += aa[i][j];

}

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

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

{

scanf ("%d", &bb[i][j]);

numsup[j] += bb[i][j];

}

bool is_valid = true;

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

if (numneed[i] > numsup[i])

{

is_valid = false;

break;

}

int ans = 0;

for (int k = 1; k <= K; k++)

{

Init ();

int val;

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

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

{

scanf ("%d", &val);

AddEdge (val, num + j, i, INF);

}

N = num + M + 2;

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

AddEdge (0, 0, num + i, bb[i][k]);

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

AddEdge (0, i, N - 1, aa[i][k]);

MinCostMaxFlow (0, N - 1);

ans += allcost;

}

if (!is_valid)

puts ("-1");

else

printf ("%d\n", ans);

}

return 0;

}

poj2195

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

04 4月 2016

Going Home

On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.

Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a '.' means an empty space, an 'H' represents a house on that point, and am 'm' indicates there is a little man on that point.
You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.

Input

There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.

Output

For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.

Sample Input

2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0

Sample Output

Source

Pacific Northwest 2004

题目类型：最小费用最大流

算法分析：从每个人开始bfs找到所有的房子，从这个人向这个房子连一条容量为1，花费为两者距离的有向边，然后从源点向每个人连一条容量为1，花费为0的有向边，从每个房子向汇点连一条容量为1，花费为0的有向边，最后跑个最小费用流即可

/*************************************************
Author        :supermaker
Created Time  :2016/4/4 20:01:51
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

struct Node
{
	int to, nxt, c, f, cost;	
	Node () {}
	Node (int tt, int nn, int cc, int ff, int cco) : to (tt), nxt (nn), c (cc), f (ff), cost (cco) {}
};

Node edge[maxn*maxn];
int head[maxn], edgelen;

void Init ()
{
	memset (head, -1, sizeof (head));
	memset (edge, -1, sizeof (edge));
	edgelen = 0;
}

void AddEdge (int cost, int u, int v, int w, int rw = 0)
{
	edge[edgelen].to = v, edge[edgelen].c = w, edge[edgelen].f = 0;
	edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++;
	edge[edgelen].to = u, edge[edgelen].c = rw, edge[edgelen].f = 0;
	edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++;
}

int dis[maxn], cnt[maxn], inq[maxn], par[maxn];
int N;

bool spfa (int s, int e)
{
	for (int i = 0; i <= N; i++)
	{
		dis[i] = INF;
		inq[i] = cnt[i] = 0;
		par[i] = -1;
	}
	dis[s] = 0;
	queue <int> qu;
	qu.push (s);
	inq[s]++, cnt[s]++;
	while (!qu.empty ())
	{
		int u = qu.front (); qu.pop (); inq[u]--;
		if (cnt[u] > N) return false;
		for (int i = head[u]; i != -1; i = edge[i].nxt)
		{
			int v = edge[i].to;
			if (edge[i].c > edge[i].f && dis[u] < INF && dis[v] > dis[u] + edge[i].cost)
			{
				dis[v] = dis[u] + edge[i].cost;
				par[v] = i;
				if (!inq[v])
				{
					qu.push (v);
					inq[v]++, cnt[v]++;
				}
			}
		}
	}
	if (par[e] == -1) return false;
	return true;
}

int allcost;
int MinCostMaxFlow (int s, int e)
{
	int res = 0;
	allcost = 0;
	while (spfa (s, e))
	{
		int minval = INF;
		for (int i = par[e]; i != -1; i = par[edge[i^1].to])
			minval = min (minval, edge[i].c - edge[i].f);
		for (int i = par[e]; i != -1; i = par[edge[i^1].to])
		{
			edge[i].f += minval;
			edge[i^1].f -= minval;
			allcost += edge[i].cost * minval;
		}
		res += minval;
	}
	return res;
}

char g[maxn][maxn];
int id[maxn][maxn], len, row, col;
bool vis[maxn][maxn];

inline bool InLine (int x, int y)
{
	if (x >= 1 && x <= row && y >= 1 && y <= col) return true;
	return false;
}

void bfs (int x, int y)
{
	memset (vis, false, sizeof (vis));
	vis[x][y] = true;
	queue <Node> qu;
	qu.push (Node (x, y, 0, 0, 0));
	while (!qu.empty ())
	{
		Node tt = qu.front (); qu.pop ();	
		if (g[tt.to][tt.nxt] == 'H')
		{
			AddEdge (tt.c, id[x][y], id[tt.to][tt.nxt], 1);
			//cout << id[x][y] << " " << id[tt.to][tt.nxt] << " " << tt.c << endl;
		}
		for (int i = 0; i < 4; i++)
		{
			int xx = tt.to + dx[i], yy = tt.nxt + dy[i];
			if (InLine (xx, yy) && !vis[xx][yy])
			{
				vis[xx][yy] = true;
				qu.push (Node (xx, yy, tt.c + 1, 0, 0));
			}
		}
	}
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &row, &col) != EOF)
	{
		if (row == 0 && col == 0) break;

		memset (id, -1, sizeof (id));
		len = 1;
		for (int i = 1; i <= row; i++)
			for (int j = 1; j <= col; j++)
			{
				scanf (" %c", &g[i][j]);
				if (g[i][j] != '.')
					id[i][j] = len++;
			}
		
		Init ();
		for (int i = 1; i <= row; i++)
			for (int j = 1; j <= col; j++)
				if (g[i][j] == 'm')
					bfs (i, j);
		len--;
		N = len + 2;
		for (int i = 1; i <= row; i++)
			for (int j = 1; j <= col; j++)
			{
				if (g[i][j] == 'm')
					AddEdge (0, 0, id[i][j], 1);
				else if (g[i][j] == 'H')
					AddEdge (0, id[i][j], len + 1, 1);
			}
		MinCostMaxFlow (0, len + 1);
		printf ("%d\n", allcost);
	}
    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

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

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

/*************************************************

Author :supermaker

Created Time :2016/4/4 20:01:51

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 200 + 66;

const int dx[] = {0, 0, -1, 1};

const int dy[] = {-1, 1, 0, 0};

struct Node

{

int to, nxt, c, f, cost;

Node () {}

Node (int tt, int nn, int cc, int ff, int cco) : to (tt), nxt (nn), c (cc), f (ff), cost (cco) {}

};

Node edge[maxn*maxn];

int head[maxn], edgelen;

void Init ()

{

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

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

edgelen = 0;

}

void AddEdge (int cost, int u, int v, int w, int rw = 0)

{

edge[edgelen].to = v, edge[edgelen].c = w, edge[edgelen].f = 0;

edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++;

edge[edgelen].to = u, edge[edgelen].c = rw, edge[edgelen].f = 0;

edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++;

}

int dis[maxn], cnt[maxn], inq[maxn], par[maxn];

int N;

bool spfa (int s, int e)

{

for (int i = 0; i <= N; i++)

{

dis[i] = INF;

inq[i] = cnt[i] = 0;

par[i] = -1;

}

dis[s] = 0;

queue <int> qu;

qu.push (s);

inq[s]++, cnt[s]++;

while (!qu.empty ())

{

int u = qu.front (); qu.pop (); inq[u]--;

if (cnt[u] > N) return false;

for (int i = head[u]; i != -1; i = edge[i].nxt)

{

int v = edge[i].to;

if (edge[i].c > edge[i].f && dis[u] < INF && dis[v] > dis[u] + edge[i].cost)

{

dis[v] = dis[u] + edge[i].cost;

par[v] = i;

if (!inq[v])

{

qu.push (v);

inq[v]++, cnt[v]++;

}

if (par[e] == -1) return false;

return true;

}

int allcost;

int MinCostMaxFlow (int s, int e)

{

int res = 0;

allcost = 0;

while (spfa (s, e))

{

int minval = INF;

for (int i = par[e]; i != -1; i = par[edge[i^1].to])

minval = min (minval, edge[i].c - edge[i].f);

for (int i = par[e]; i != -1; i = par[edge[i^1].to])

{

edge[i].f += minval;

edge[i^1].f -= minval;

allcost += edge[i].cost * minval;

}

res += minval;

}

return res;

}

char g[maxn][maxn];

int id[maxn][maxn], len, row, col;

bool vis[maxn][maxn];

inline bool InLine (int x, int y)

{

if (x >= 1 && x <= row && y >= 1 && y <= col) return true;

return false;

}

void bfs (int x, int y)

{

memset (vis, false, sizeof (vis));

vis[x][y] = true;

queue <Node> qu;

qu.push (Node (x, y, 0, 0, 0));

while (!qu.empty ())

{

Node tt = qu.front (); qu.pop ();

if (g[tt.to][tt.nxt] == 'H')

{

AddEdge (tt.c, id[x][y], id[tt.to][tt.nxt], 1);

//cout << id[x][y] << " " << id[tt.to][tt.nxt] << " " << tt.c << endl;

}

for (int i = 0; i < 4; i++)

{

int xx = tt.to + dx[i], yy = tt.nxt + dy[i];

if (InLine (xx, yy) && !vis[xx][yy])

{

vis[xx][yy] = true;

qu.push (Node (xx, yy, tt.c + 1, 0, 0));

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &row, &col) != EOF)

{

if (row == 0 && col == 0) break;

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

len = 1;

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

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

{

scanf (" %c", &g[i][j]);

if (g[i][j] != '.')

id[i][j] = len++;

}

Init ();

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

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

if (g[i][j] == 'm')

bfs (i, j);

len--;

N = len + 2;

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

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

{

if (g[i][j] == 'm')

AddEdge (0, 0, id[i][j], 1);

else if (g[i][j] == 'H')

AddEdge (0, id[i][j], len + 1, 1);

}

MinCostMaxFlow (0, len + 1);

printf ("%d\n", allcost);

}

return 0;

}

poj3422

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

02 4月 2016

Kaka's Matrix Travels

On an N × N chessboard with a non-negative number in each grid, Kaka starts his matrix travels with SUM = 0. For each travel, Kaka moves one rook from the left-upper grid to the right-bottom one, taking care that the rook moves only to the right or down. Kaka adds the number to SUM in each grid the rook visited, and replaces it with zero. It is not difficult to know the maximum SUM Kaka can obtain for his first travel. Now Kaka is wondering what is the maximum SUM he can obtain after his Kth travel. Note the SUM is accumulative during the Ktravels.

Input

The first line contains two integers N and K (1 ≤ N ≤ 50, 0 ≤ K ≤ 10) described above. The following N lines represents the matrix. You can assume the numbers in the matrix are no more than 1000.

Output

The maximum SUM Kaka can obtain after his Kth travel.

Sample Input

3 2
1 2 3
0 2 1
1 4 2

Sample Output

Source

POJ Monthly--2007.10.06, Huang, Jinsong

题目类型：最小费用最大流

算法分析：建图时需要拆点，将每个点A拆成点A’和点A”，从A’向A”先连一条容量为1，花费为该点值的有向边，再连一条容量为k-1，花费为0的有向边(第一条边表示第一次到达该位置时可以拿走cost价值的东西，第二条边表示该点在拿完之后没有了，但是可以走k-1步)。若A点存在右边相邻或者是下面相邻的点B，则从A”向B’连一条容量为k，花费为0的有向边。最后再分别建一个源点和汇点，源点和1”相连容量为k，花费为0，2*n*n + 1和汇点相连容量为k，花费为0。最后跑一个最小费用流即可。注意这里边表的个数！！！

/*************************************************
Author        :supermaker
Created Time  :2016/4/1 20:26:51
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

struct Node
{
	int to, nxt, c, f, cost;	
};

Node edge[maxn*6];
int head[maxn], edgelen;

void Init ()
{
	memset (head, -1, sizeof (head));
	memset (edge, -1, sizeof (edge));
	edgelen = 0;
}

void AddEdge (int cost, int u, int v, int w, int rw = 0)
{
	edge[edgelen].to = v, edge[edgelen].c = w, edge[edgelen].f = 0;
	edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++;
	edge[edgelen].to = u, edge[edgelen].c = rw, edge[edgelen].f = 0;
	edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++;
}

int dis[maxn], cnt[maxn], inq[maxn], par[maxn];
int N;

bool spfa (int s, int e)
{
	for	(int i = 0; i <= N; i++)
	{
		dis[i] = INF;
		inq[i] = cnt[i] = 0;
		par[i] = -1;
	}
	dis[s] = 0;
	queue <int> qu;
	qu.push (s);
	inq[s]++, cnt[s]++;
	while (!qu.empty ())
	{
		int u = qu.front (); qu.pop (); inq[u]--;
		if (cnt[u] > N) 
		{
			DB ("hi");
			return false;	
		}

		for (int i = head[u]; i != -1; i = edge[i].nxt)
		{
			int v = edge[i].to;
			if (edge[i].c > edge[i].f && dis[u] < INF && dis[v] > dis[u] + edge[i].cost)
			{
				dis[v] = dis[u] + edge[i].cost;
				par[v] = i; 
				if (!inq[v])
				{
					qu.push (v);
					inq[v]++, cnt[v]++;
				}
			}
		}
	}
	if (par[e] == -1) return false;
	return true;
}

int allcost;
int MinCostMaxFlow (int s, int e)
{
	int res = 0;
	allcost = 0;
	while (spfa (s, e))
	{
		int minval = INF;
		for (int i = par[e]; i != -1; i = par[edge[i^1].to])
			minval = min (minval, edge[i].c - edge[i].f);
		for (int i = par[e]; i != -1; i = par[edge[i^1].to])
		{
			edge[i].f += minval;
			edge[i^1].f -= minval;
			allcost += edge[i].cost * minval;
		}
		res += minval;
		//DB (res);
	}
	return res;
}

int g[66][66];

int main()
{
    //CFF;
    //CPPFF;
   	int n, k;
	while (scanf ("%d%d", &n, &k) != EOF)
	{
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				scanf ("%d", &g[i][j]);
		Init ();
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				int u = (i - 1) * n + j;
				AddEdge (-g[i][j], u, u + n * n, 1);
				AddEdge (0, u, u + n * n, k - 1);
				if (i + 1 <= n)
					AddEdge (0, u + n * n, u + n, k);
				if (j + 1 <= n)
					AddEdge (0, u + n * n, u + 1, k);
				//DB (u), DB (u + n * n);
			}
		
		AddEdge (0, 0, 1, k);
		AddEdge (0, 2 * n * n, 2 * n * n + 1, k);
		N = 2 * n * n + 2;
		MinCostMaxFlow (0, 2 * n * n + 1);
		printf ("%d\n", -allcost);
	}
    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

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

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

/*************************************************

Author :supermaker

Created Time :2016/4/1 20:26:51

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#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;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 6000 + 66;

struct Node

{

int to, nxt, c, f, cost;

};

Node edge[maxn*6];

int head[maxn], edgelen;

void Init ()

{

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

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

edgelen = 0;

}

void AddEdge (int cost, int u, int v, int w, int rw = 0)

{

edge[edgelen].to = v, edge[edgelen].c = w, edge[edgelen].f = 0;

edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++;

edge[edgelen].to = u, edge[edgelen].c = rw, edge[edgelen].f = 0;

edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++;

}

int dis[maxn], cnt[maxn], inq[maxn], par[maxn];

int N;

bool spfa (int s, int e)

{

for (int i = 0; i <= N; i++)

{

dis[i] = INF;

inq[i] = cnt[i] = 0;

par[i] = -1;

}

dis[s] = 0;

queue <int> qu;

qu.push (s);

inq[s]++, cnt[s]++;

while (!qu.empty ())

{

int u = qu.front (); qu.pop (); inq[u]--;

if (cnt[u] > N)

{

DB ("hi");

return false;

}

for (int i = head[u]; i != -1; i = edge[i].nxt)

{

int v = edge[i].to;

if (edge[i].c > edge[i].f && dis[u] < INF && dis[v] > dis[u] + edge[i].cost)

{

dis[v] = dis[u] + edge[i].cost;

par[v] = i;

if (!inq[v])

{

qu.push (v);

inq[v]++, cnt[v]++;

}

if (par[e] == -1) return false;

return true;

}

int allcost;

int MinCostMaxFlow (int s, int e)

{

int res = 0;

allcost = 0;

while (spfa (s, e))

{

int minval = INF;

for (int i = par[e]; i != -1; i = par[edge[i^1].to])

minval = min (minval, edge[i].c - edge[i].f);

for (int i = par[e]; i != -1; i = par[edge[i^1].to])

{

edge[i].f += minval;

edge[i^1].f -= minval;

allcost += edge[i].cost * minval;

}

res += minval;

//DB (res);

}

return res;

}

int g[66][66];

int main()

{

//CFF;

//CPPFF;

int n, k;

while (scanf ("%d%d", &n, &k) != EOF)

{

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

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

scanf ("%d", &g[i][j]);

Init ();

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

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

{

int u = (i - 1) * n + j;

AddEdge (-g[i][j], u, u + n * n, 1);

AddEdge (0, u, u + n * n, k - 1);

if (i + 1 <= n)

AddEdge (0, u + n * n, u + n, k);

if (j + 1 <= n)

AddEdge (0, u + n * n, u + 1, k);

//DB (u), DB (u + n * n);

}

AddEdge (0, 0, 1, k);

AddEdge (0, 2 * n * n, 2 * n * n + 1, k);

N = 2 * n * n + 2;

MinCostMaxFlow (0, 2 * n * n + 1);

printf ("%d\n", -allcost);

}

return 0;

}

超客的水墨烟雨

poj1742

poj3280

poj2718

poj3262

poj3040

poj3187

BestCoder Round #78(Div.2) (0/4) (Div.1) (0/4)

poj1966

poj2125

poj2175

poj2516

poj2195

poj3422

分类目录

标签云

书签

近期评论

2016年4月
一	二	三	四	五	六	日
« 3月				2月 »
				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