SPOJ 412 K-path cover 匹配
http://hi.baidu.com/roba/blog/item/c842fdfac10d24dcb48f31d7.html
roba的解说
题目链接
题目大意就是说，给N个点，每个点都有一个权值，某些点之间存在有向边，有向边的权值为它的两端点权值之和。现在要求从中选出K条边，使得没有任何两条边共头或共尾，问K条边的权值和最小为多少。数据范围大的吓人，N<=10^4，边数M<=10^6，但是K<=100。
容易想到一个网络流(or 匹配?)的做法，就是把每个点p拆成两个(p,p')，然后对于原图中的边(u,v)，在新图中加边(u,v')，权值不变。这样问题就转化为在新的二分图中求出一个包含K条边的最小带权匹配。这个问题可以转化成最小费用流解决：添加源和汇，源到所有左子集的点添加容量为1，费用为0的边；所有右子集到汇添加容量为1，费用为0的边；中间的边容量为1，费用为原权值。然后求一个流值为K的最小费用流。
然而常用的最小费用流算法复杂度太高，比如用Bellman-Ford找最小费用路，那么复杂度就高达O(MNK)，显然不可接受。到网上四处去问，Jin Bin大牛给了一个ahyangyi的解答，是贪心一个初始流，先选出尽可能小的K条边，另外Adrian Kuegel给了一个非常漂亮的解法，简述如下：
朴素的费用流算法没有利用到题目中“边的权值是它的两端点权值之和”这一条件。考虑一下类似匈牙利算法找交错链的过程，实际上，在这个条件下，可以发现每次增广后增加的费用就是新加入匹配的两个点的权值。比如当前的匹配是(b,a)，现在发现一条交错链(c,a),(a,b),(b,d)，则增广后新的匹配变为(c,a),(b,d)，增加的权值就是c点和d点的权值。由于这个特点，我们可以在每次增广的时候，枚举左子集中当前未匹配的点作为起点，用BFS或DFS查找交错链，记录下每条交错链的起点和终点的权值和，在所有这些权值和中取最小的一对进行增广。注意如果把点按权值排序后，每个点就只须访问一次，故每次增广的时间复杂度就是遍历图的O(M+N)，共需增广K次，故总的复杂度为O((M+N)*K)。
OK,然后是代码
#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <queue>#include <map>#include <set>#define eps 1e-5#define MAXN 11111#define MAXM 1111111#define INF 1000000007using namespace std;int k, n, m;struct P{ int w, id; bool operator <(const P &a)const { return w < a.w; }}p[MAXN];struct EDGE{ int v, next;}edge[MAXM];int head[MAXN], e;int id[MAXN], used[MAXN], lx[MAXN], ly[MAXN], fa[MAXN], ha[MAXN];int ans;void init(){ e = 0; ans = 0; memset(head, -1, sizeof(head)); memset(used, 0, sizeof(used)); memset(lx, 0, sizeof(lx)); memset(ly, 0, sizeof(ly));}void add(int x, int y){ edge[e].v = y; edge[e].next = head[x]; head[x] = e++;}void dfs(int u, int f){ for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(!fa[v]) { fa[v] = u; if(!ly[v]) ha[v] = f; else dfs(ly[v], f); } }}bool find(){ memset(fa, 0, sizeof(fa)); for(int i = 1; i <= n; i++) if(!used[i]) dfs(i, i); int mi = INF, pos = -1; for(int i = 1; i <= n; i++) if(!ly[i] && fa[i]) if(mi > p[i].w + p[ha[i]].w) { mi = p[i].w + p[ha[i]].w; pos = i; } if(pos == -1) return 0; ans += mi; int u; for(u = pos; fa[u] != ha[pos];) { ly[u] = fa[u]; int tmp = lx[fa[u]]; lx[fa[u]] = u; u = tmp; } ly[u] = ha[pos]; lx[ha[pos]] = u; used[ha[pos]] = 1; return 1;}int main(){ int T; scanf("%d", &T); while(T--) { scanf("%d%d%d", &k, &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &p[i].w), p[i].id = i; sort(p + 1, p + n + 1); for(int i = 1; i <= n; i++) id[p[i].id] = i; int u, v; init(); for(int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); add(id[u], id[v]); } int flag = 1; for(int i = 1; i <= k; i++) if(!find()){flag = 0; break;} if(!flag) printf("NONE\n"); else printf("%d\n", ans); } return 0;}