wannafly-day1 Problem A

思路：队友贪心WA了，然后就没有然后了，自己也是第一次接触最小费用流的题。借这个题来学习一下，利用Spfa每次来找到一个最短的路径同时保存路径，每一次寻找最短路径就将这条路的最小费用流给剪掉，然后继续下次寻找最短路径。

附上代码，参考了网上，

#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>

using namespace std;

const int maxn = 5e3 + 5;
const int INF = 0x3f3f3f3f;
struct Edge{
    int value, flow, to, rev;
    Edge(){}
    Edge(int a, int b, int c, int d) :to(a), value(b), flow(c), rev(d){}
};
vector<Edge> vec[maxn];
inline void Add(int from, int to, int flow, int value){
    vec[from].push_back(Edge(to, value, flow, vec[to].size()));
    vec[to].push_back(Edge(from, -value, 0, vec[from].size() - 1));
}
bool book[maxn];//用于SPFA中标记是否在queue中
int cost[maxn];//用于存费用的最短路径
int pre[maxn];//用于存前结点
int pree[maxn];//用于存钱结点的vector中的下标

bool Spfa(int from, int to){
    memset(book, false, sizeof book);
    memset(cost, INF, sizeof cost);
    book[from] = true;
    //cout << cost[0] << " " << INF << endl;
    cost[from] = 0;
    queue<int>que;
    que.push(from);
    while (!que.empty()){
        int t = que.front();
        book[t] = false;
        que.pop();
        for (int i = 0; i < vec[t].size(); i++){
            Edge& e = vec[t][i];
            if (e.flow>0 && cost[e.to] > cost[t] + e.value){
                cost[e.to] = cost[t] + e.value;
                pre[e.to] = t;
                pree[e.to] = i;
                if (book[e.to] == false){
                    que.push(e.to);
                    book[e.to] = true;
                }
            }
        }
    }
    return cost[to] != INF;
}
int Work(int from, int to){
    int sum = 0;
    while (Spfa(from, to)){
        int mflow = INF;//SPFA找到最短路径的最小容量
        int flag = to;
        while (flag != from){
            mflow = min(mflow, vec[pre[flag]][pree[flag]].flow);
            flag = pre[flag];
        }
        flag = to;
        while (flag != from){
            //cout << flag << " " << pre[flag] << " " << mflow << " " << vec[pre[flag]][pree[flag]].value << endl;
            sum += vec[pre[flag]][pree[flag]].value*mflow;
            vec[pre[flag]][pree[flag]].flow -= mflow;
            vec[flag][vec[pre[flag]][pree[flag]].rev].flow += mflow;
            flag = pre[flag];
        }
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);

    int n, m, a, b; 
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a >> b;
        Add(i, a + n, 1, 0);
        Add(i, b + n, 1, 0);
        Add(0, i, 1, 0);
    }
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= 99; j += 2){
            Add(i + n, m + n + 1, 1, j);
        }
    }
    cout << Work(0, m + n + 1) << endl;
    
    return 0;
}