首页 > 代码库 > UVA 10330 Power Transmission
UVA 10330 Power Transmission
题意:懒得打了。LUCKY CAT 里有 http://163.32.78.26/homework/q10330.htm
第一个网络流题目。每个节点都有一个容量值。需要拆点。拆成i - > i + N 边权为容量值
另外注意B个点 连接方式:s - 集合B
D个点 链接方式 集合D + N -> t汇点
其他看处理就好
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 250const int INF = 0x3f3f3f3f ;int flow[MAXN][MAXN],c[MAXN][MAXN];int p[MAXN];int N,M,B,D,src,tag;void read(){ memset(c,0,sizeof(c)); src = 0; tag = 2 * N + 1; for (int i = 1; i <= N; i++) { int tmp; scanf("%d",&tmp); c[i][i + N] = tmp; } scanf("%d",&M); for (int i = 1; i <= M; i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); c[u + N][v] = w; } scanf("%d%d",&B,&D); for (int i = 1; i <= B; i++) { int tmp; scanf("%d",&tmp); c[0][tmp] = INF; } for (int i = 1; i <= D; i++) { int tmp; scanf("%d",&tmp); c[tmp + N][tag] = INF; }}int Edmonds_karp(int src,int tag){ memset(flow,0,sizeof(flow)); int ans = 0; queue<int>q; while (!q.empty()) q.pop(); int a[MAXN]; while (true) { memset(a,0,sizeof(a)); a[src] = INF; q.push(src); while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 0; v <= tag; v++) if (!a[v] && c[u][v] > flow[u][v]) { p[v] = u; q.push(v); a[v] = min(a[u],c[u][v] - flow[u][v]); } } if (a[tag] == 0) break; for (int u = tag; u != src; u = p[u]) { flow[p[u]][u] += a[tag]; flow[u][p[u]] -= a[tag]; } ans += a[tag]; } return ans;}int main(){ //freopen("sample.txt","r",stdin); while (scanf("%d",&N)!=EOF) { read(); printf("%d\n",Edmonds_karp(src,tag)); } return 0;}
UVA 10330 Power Transmission
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。