二分图最大匹配，HK算法，暴力枚举

题意：

分析：

这道题是很明显是二分匹配题目。但因为我初学二分图所以刚开始并没有看出如何建立二分图的。
我是想，对于人：1,2,3,4,5,6,7,8
在刚开始匹配，1去将他手中的一个任务交给5
然后到2开始交任务，如果2也有一个要交给5的任务，那么此时他发现5已经有任务了！
所以，我们要看1，能不能将5的任务收回找别人交？

其实，这就是一个寻找增广路的过程！！！所以，二分图的做法自然就出来了。
我们建立二分图：
1 1
2 2
3 3
4 4
5 5
如上所示。

然后，算他的最大匹配就ok了。
但是，要判断哪些点是必须不能去掉的点却好麻烦。。。我不会强连通分量，所以只能暴力枚举。。。。。
依次去掉 一个边看最大匹配有没有变化。。。。。我是废物，，

因为我选择枚举，所以时间复杂的直接高了一个次方。再用匈牙利算法就不太保险了。但似乎也能过？
我用的HK算法。总复杂度为O(n^2.5)

n最大为500故n^2.5 = * 10^6

还不到10^7，勉勉强强。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef pair<int, int> pii;
const int inf = 2e9;
const int max_n = 510;
const int max_m = 20010;
struct edge {
    int to, next; 
}E[max_m * 2];
int head[max_n];
int cnt = 1;
int n, m;


void add(int from, int to) {
    E[cnt].to = to;
    E[cnt].next = head[from];
    head[from] = cnt++;
}

int eu = -1, ev = -1;


int distright[max_n], distleft[max_n];
int rightTo[max_n], leftTo[max_n];
int dist;

bool searchpath() {
    fill(distright, distright + 1 + n, -1);
    fill(distleft, distleft + 1 + n, -1);
    queue<int> que;dist = inf;
    for (int i = 1;i <= n;i++)
        if (rightTo[i] == -1)que.push(i);
    while (!que.empty()) {
        int u = que.front();que.pop();
        if (distright[u] > dist)break;
        for (int i = head[u];i;i = E[i].next) {
            int v = E[i].to;
            if (u == eu && v == ev)continue;
            if (distleft[v] != -1)continue;
            distleft[v] = distright[u] + 1;
            if (leftTo[v] == -1)dist = distleft[v];
            else {
                distright[leftTo[v]] = distleft[v] + 1;
                que.push(leftTo[v]);
            }
        }
    }return dist != inf;
}
bool matchpath(int u) {
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (u == eu && v == ev)continue;
        if (distleft[v] != distright[u] + 1)continue;
        if (distleft[v] == dist && leftTo[v] != -1)continue;
        distleft[v] = -1;
        if (leftTo[v] == -1 || matchpath(leftTo[v])) {
            leftTo[v] = u;rightTo[u] = v;
            return true;
        }
    }return false;
}

int HK() {
    fill(leftTo, leftTo + 1 + n, -1);
    fill(rightTo, rightTo + 1 + n, -1);
    int ans = 0;
    while (searchpath()) {
        for (int i = 1;i <= n;i++) {
            if (rightTo[i] == -1 && matchpath(i))
                ans++;
        }
    }
    return ans;
}



int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    fill(head, head + n + 1, false);
    map<pii, int>m1;map<pii, int>m2;
    for (int i = 1;i <= m;i++) {
        int u, v;cin >> u >> v;
        pii p = { u,v };
        m2[p]++;
        if (m2[p] > 1)continue;
        add(u, v);m1[p] = i;
    }
    int ans = HK();
    vector<pii> es;
    for (int i = 1;i <= n;i++) {
        if (rightTo[i] == -1)continue;
        es.push_back({ i,rightTo[i] });
    }
    vector<int> res;
    for (int i = 0;i < es.size();i++) {
        eu = es[i].first;ev = es[i].second;
        pii p = { eu,ev };
        if (m2[p] > 1)continue;
        if (HK() != ans)
            res.push_back(m1[p]);
    }
    cout << ans << " " << res.size() << endl;
    sort(res.begin(), res.end());
    for (int i = 0;i < res.size();i++)
        cout << res[i] << endl;
}

话说，有重边的有木有，，，没注意。错了几次。。。。。。