poj3469

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

12 2月 2016

Dual Core CPU

As more and more computers are equipped with dual core CPU, SetagLilb, the Chief Technology Officer of TinySoft Corporation, decided to update their famous product - SWODNIW.

The routine consists of N modules, and each of them should run in a certain core. The costs for all the routines to execute on two cores has been estimated. Let's define them as A_i and B_i. Meanwhile, M pairs of modules need to do some data-exchange. If they are running on the same core, then the cost of this action can be ignored. Otherwise, some extra cost are needed. You should arrange wisely to minimize the total cost.

Input

There are two integers in the first line of input data, N and M (1 ≤ N ≤ 20000, 1 ≤ M ≤ 200000) .
The next N lines, each contains two integer, A_i and B_i.
In the following M lines, each contains three integers: a, b, w. The meaning is that if module a and module b don't execute on the same core, you should pay extra w dollars for the data-exchange between them.

Output

Output only one integer, the minimum total cost.

Sample Input

3 1
1 10
2 10
10 3
2 3 1000

Sample Output

Source

POJ Monthly--2007.11.25, Zhou Dong

题目类型：最小割

算法分析：将芯片1看作是源点，芯片2看作是汇点。从源点向每个模块连一条权值为Ai的有向边，每个模块向汇点连接一条权值为Bi的有向边。对于两个模块之间存在额外共享数据的情况，则在两个模块之间连接无向边。最后跑一个最大流即可

/*************************************************
Author        :supermaker
Created Time  :2016/2/12 17:53:44
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 = 1e6 + 66;

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

Node edge[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].to = v, edge[edgelen].c = w, edge[edgelen].f = 0;
	edge[edgelen].nxt = head[u], head[u] = edgelen++;
	edge[edgelen].to = 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].to;
			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].to;
		}
		else
		{
			bool is_have = false;
			for (int i = cur[u]; i != -1; i = edge[i].nxt)
			{
				int v = edge[i].to;
				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].to] < minval)
				{
					minval = dep[edge[i].to];
					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].to;
		}
	}
	return res;
}

int main()
{
    //CFF;
    //CPPFF;
	int n, m;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		Init ();
		for (int i = 1; i <= n; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			AddEdge (0, i, u);
			AddEdge (i, n + 1, v);
		}
		for (int i = 1; i <= m; i++)
		{
			int u, v, w;
			scanf ("%d%d%d", &u, &v, &w);
			AddEdge (u, v, w);
			AddEdge (v, u, w);
		}
		printf ("%d\n", MaxFlow (0, n + 1, n + 2));
	}
    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

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

Author :supermaker

Created Time :2016/2/12 17:53:44

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 = 1e6 + 66;

struct Node

{

int to, nxt, c, f;

};

Node edge[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].to = v, edge[edgelen].c = w, edge[edgelen].f = 0;

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

edge[edgelen].to = 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].to;

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].to;

}

else

{

bool is_have = false;

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

{

int v = edge[i].to;

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].to] < minval)

{

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

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].to;

}

return res;

}

int main()

{

//CFF;

//CPPFF;

int n, m;

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

{

Init ();

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

{

int u, v;

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

AddEdge (0, i, u);

AddEdge (i, n + 1, v);

}

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

{

int u, v, w;

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

AddEdge (u, v, w);

AddEdge (v, u, w);

}

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

}

return 0;

}

poj1637

poj1780

超客的水墨烟雨

poj3469

分类目录

标签云

书签

近期评论

2024年5月
一	二	三	四	五	六	日
« 6月
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31