A simple Blog for wyx I've been down the bottle hoping.
4883: [Lydsy2017年5月月赛]棋盘上的守卫 Kruskal
发表于: | 分类: Oi | 评论:0 | 阅读:74

左侧$n$个点右侧$m$个点中间连$a_{i,j}$的费用

然后跑费用流

然后考虑直接$Kruskal$就行了,注意到我们求得是最小环套树森林哦……所以是可以存在一个环的,但是环和环直接是不能合并的

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200000+5;
const int M = N;
int F[N], stack[N];
bool v[N];

inline int find(int x) {
    while(F[x] != x && F[x]) {
        stack[++stack[0]] = x;
        x = F[x];
    }
    F[x] = x;
    while(stack[0]) 
        F[stack[stack[0]--]] = x;
    return x;
}

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct data {
    int x, y, val;
    data () {}
    data (int _x,int _y,int _val):x(_x),y(_y),val(_val) {}
    bool operator < (const data &z) const {
        return val < z.val;
    }
} edge[M];

int size[N];

int main() {
    int n = read(), m = read(), z;
    int top = 0;
    register int i, j;
    for(i=1;i<=n;++i) {
        for(j=1;j<=m;++j) {
            z = read();
            edge[++top] = data(i, j+n, z);
        }
    }
    for(int i=1;i<=n+m;++i) size[i] = 1;
    sort(edge+1,edge+top+1);
    long long ans = 0;
    for(i=1;i<=top;++i) {
        int x = find(edge[i].x), y =find(edge[i].y);
        if(v[x] && v[y]) continue;
        if(x != y) {
            v[y] |= v[x];
            F[F[x]] = y;
        }
        else v[x] = 1;
        ans += edge[i].val;
    }
    cout << ans << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP