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