HDU5294——SPFA+最小割Dinic算法——Tricks Device

http://acm.hdu.edu.cn/showproblem.php?pid=5294

SPFA：

Bellman_Ford的队列优化算法

无法处理带负环的图

复杂度O（kE）  k <= 2

Dinic 算法

O(n^2*m）

先BFS找到层次图，如果在这个层次图里面无法再访问到n说明找不到增广路

层次图就相当于可以进行增广的图，但是不知道增广到什么程度

相当于EK算法中从0遍历到n

然后就DFS找增广路

当权值为1时 最大流= 最小割

可以当做模板

/************************************************
* Author        :Powatr
* Created Time  :2015-8-26 13:04:46
* File Name     :spfa+dinic.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 2e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

int cnt[MAXN];
int it[MAXN];
int d[MAXN];
bool vis[MAXN];
int check[MAXN];
struct edge{
    int v, w;
};
struct edge1{
    int v,  rev,  dir;
};
queue<int> q;
vector<edge> G[MAXN];
vector<edge1> F[MAXN];
int n, m;
void add_edge(int u, int v)
{
    int len1 = F[v].size(), len2 = F[u].size();
    F[u].push_back((edge1){v, len1, 1});//因为开了结构体F[i][j]不再是下一个点的u，所以要记录下位置
    F[v].push_back((edge1){u, len2 - 1, 0});
}

void SPFA()
{
    memset(vis, false, sizeof(vis));
    vis[1] = true;
    for(int i = 1; i <= n; i++){
        d[i] = cnt[i] = INF;
    }
    d[1] = cnt[1] = 0;
    while(!q.empty()) q.pop();   
    q.push(1);
    while(!q.empty()){
        int u = q.front(); q.pop();
        vis[u] = false;//入队的点开始不能确定是最优的
        for(int i = 0; i < G[u].size(); i++){
            int v = G[u][i].v, w = G[u][i].w;
             if(d[v] == d[u] + w) {
                cnt[v] = min(cnt[v], cnt[u] + 1);
             }
             if(d[v] > d[u] + w){
                 d[v] = d[u] + w;
                 cnt[v] = cnt[u] + 1;
                 if(!vis[v]){
                     vis[v] = true;
                     q.push(v);
                }
            }
        }
    }
}


void build_gragh()
{//对于最短路再建一张图
    for(int i = 1; i <= n; i++){
        for(int j = 0 ; j < G[i].size(); j++){
            edge &e = G[i][j];
            if(d[i] + e.w == d[e.v]){
               add_edge(i, e.v);
            }
        }
    }
}

int BFS()
{//得带层次图
    memset(check, -1, sizeof(check));
    while(!q.empty()) q.pop();
    check[1] = 0;
    q.push(1); 
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = 0 ;i < F[u].size(); i++){
            edge1 &e = F[u][i];
            if(e.dir > 0 && check[e.v] < 0){//正向
                check[e.v] = check[u] + 1;
                q.push(e.v);
            }
        }
    }
    if(check[n] != -1) return 1;
    return 0;
}
        
int DFS(int u, int f)
{//增广
    if(u == n) return f;
    for(int i = it[u]; i < F[u].size(); i++){//增广路优化，如果访问过下一个直接跳过来
        it[u] = i;
        edge1 &e = F[u][i];
        if(e.dir > 0 && check[e.v] ==  check[u] + 1 ){
            int d= DFS(e.v, min(f, e.dir));
            if(d > 0){
                e.dir -= d;
                F[e.v][e.rev].dir += d;//得到反向边
                return d;
            }
        }
    }
    return 0;
}
int Dinic()
{
    int flow = 0, f;
    while(BFS()){//对于一个层次图能进行多次增广
        memset(it, 0, sizeof(it));
        while((f = DFS(1,INF)) > 0){
            flow += f;
        }
    }
    return flow;
}



int main(){
    while(~scanf("%d%d", &n, &m)){
        int u, v, w;
        for(int i = 1; i <= n; i++){
            G[i].clear();
            F[i].clear();
        }
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d", &u, &v, &w);
            G[u].push_back((edge){v, w});
            G[v].push_back((edge){u, w});
        }
        SPFA();
        build_gragh();
        int ans =  Dinic();
        printf("%d %d
", ans, m - cnt[n]);
    }
    return 0;
}