首页 > 代码库 > hdu 4494 Teamwork (可行流的最小流)
hdu 4494 Teamwork (可行流的最小流)
去年通话邀请赛的B题,当时居然过的那么少。。。明明是一道非常裸的可行流最小流麽。。仅仅要对每种人分别求一下可行最小流加起来就能够了。建图是对每一个点拆点,容量上下届都设为v[i],然后每一个点间能连边的直接连边就能够了。然后在这个图的基础上转化为可行流最小流,求一下就能够了。。。
#include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<cstdio> #include<cmath> #include<queue> #include<stack> #include<map> #include<set> #define LL long long #define inf 0x3f3f3f3f #define CLR(a, b) memset(a, b, sizeof(a)) using namespace std; const int maxn = 440; const int INF = 0x3f3f3f3f; struct Edge { int from, to, cap, flow; Edge() {} Edge(int from, int to, int cap, int flow) :from(from), to(to), cap(cap), flow(flow) {} }; struct ISAP { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[maxn]; // BFS使用 int d[maxn]; // 从起点到i的距离 int cur[maxn]; // 当前弧指针 int p[maxn]; // 可增广路上的上一条弧 int num[maxn]; // 距离标号计数 void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(t); vis[t] = 1; d[t] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]^1]; if(!vis[e.from] && e.cap > e.flow) { vis[e.from] = 1; d[e.from] = d[x] + 1; Q.push(e.from); } } } return vis[s]; } void init(int n) { this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } int Augment() { int x = t, a = INF; while(x != s) { Edge& e = edges[p[x]]; a = min(a, e.cap-e.flow); x = edges[p[x]].from; } x = t; while(x != s) { edges[p[x]].flow += a; edges[p[x]^1].flow -= a; x = edges[p[x]].from; } return a; } int Maxflow(int s, int t, int need) { this->s = s; this->t = t; int flow = 0; BFS(); memset(num, 0, sizeof(num)); for(int i = 0; i < n; i++) num[d[i]]++; int x = s; memset(cur, 0, sizeof(cur)); while(d[s] < n) { if(x == t) { flow += Augment(); if(flow >= need) return flow; x = s; } int ok = 0; for(int i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow && d[x] == d[e.to] + 1) // Advance { ok = 1; p[e.to] = G[x][i]; cur[x] = i; // 注意 x = e.to; break; } } if(!ok) // Retreat { int m = n-1; // 初值注意 for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow) m = min(m, d[e.to]); } if(--num[d[x]] == 0) break; num[d[x] = m+1]++; cur[x] = 0; // 注意 if(x != s) x = edges[p[x]].from; } } return flow; } } sol; int n, m; struct Point { int x, y, b, e; int v[7]; void inpt() { scanf("%d%d%d%d", &x, &y, &b, &e); e += b; for(int i = 0; i < m; i ++) scanf("%d", &v[i]); } }p[maxn]; bool ok(Point a, Point b) { int len = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); return b.b > a.e && len <= (b.b - a.e) * (b.b - a.e); } int solve(int idx) { sol.init(n * 2 + 5); int S = 0, T = 2 * n + 1, SS = 2 * n + 2, ST = SS + 1; for(int i = 1; i <= n; i ++) { // sol.AddEdge(i, i + n, 0); sol.AddEdge(S, i, INF); sol.AddEdge(i + n, T, INF); sol.AddEdge(SS, i + n, p[i].v[idx]); sol.AddEdge(i, ST, p[i].v[idx]); } for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) { if(!ok(p[i], p[j])) continue; sol.AddEdge(i + n, j, p[i].v[idx]); } sol.Maxflow(SS, ST, INF); sol.AddEdge(T, S, INF); sol.Maxflow(SS, ST, INF); return sol.edges[sol.edges.size() - 2].flow; } int main() { int T; scanf("%d", &T); while(T --) { scanf("%d%d", &n, &m); n --; scanf("%d%d", &p[0].x, &p[0].y); p[0].b = p[0].e = 0; for(int i = 1; i <= n; i ++) p[i].inpt(); int ans = 0; for(int i = 0; i < m; i ++) ans += solve(i); printf("%d\n", ans); } }
hdu 4494 Teamwork (可行流的最小流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。