hdu 4411(最小权匹配or费用流)

题意：n个小偷在n个不同城市，某些城市之间有道路连接，k个警察在城市0，问将所有小偷抓好城市0警察所花费的最小总路程，还有一个条件是抓小偷必须按1，2,3,4……n顺序。

思路：可以用最小权匹配来做，抓每个小偷的警察必然是从小偷编号之前的那些城市过来的，所以每个城市能被你比他编号小的城市所匹配。而城市0则可以拆成个点，这k个点可以匹配任意点，也可以被任意点匹配。总体来说相当于将城市路径分解成k个环，求解这k个环的最小长度和。

费用流

建图：将每个城市拆成出点和人点，两点之间加一条容量为1，费用为-M的边，其中M要尽量大。0点到每个入点连一条容量为1费用为0的边，每个出点到汇点连接一条容量为1费用为零的边。然后0点到汇点连接一条容量为k费用为0的边，源点到0点连接一条费用为0，容量为k的边。跑最小费用最大流，结果加上M*n。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define inf 0x3f3f3f3f
#define N 505
#define M 100010
queue<int> q;
int cnt,S,T;
int net[110][110],pre[N],low[N],dist[N],p[N];
struct edge{
    int u,v,cap,cost,next;
}e[M];
void addedge(int u,int v,int cap,int cost){
    e[cnt].u=u,e[cnt].v=v,e[cnt].cap=cap,e[cnt].cost=cost,e[cnt].next=pre[u],pre[u]=cnt++;
    e[cnt].u=v,e[cnt].v=u,e[cnt].cap=0,e[cnt].cost=-cost,e[cnt].next=pre[v],pre[v]=cnt++;
}
bool spfa(){
    memset(dist,0x3f3f,sizeof(dist));
    memset(low,0,sizeof(low));
    memset(p,-1,sizeof(p));
    low[S]=inf;
    dist[S]=0;q.push(S);
    while(!q.empty()){

        int u=q.front();q.pop();
        for(int edg=pre[u];edg!=-1;edg=e[edg].next){
            int v=e[edg].v;
            if(e[edg].cap>0&&dist[v]>dist[u]+e[edg].cost){
                dist[v]=dist[u]+e[edg].cost;
                q.push(v);
                low[v]=min(e[edg].cap,low[u]);
                p[v]=edg;
            }
        }
    }
    return low[T]!=0;
}
int flowcost(){
    int ret=0;
    while(spfa()){
        ret+=low[T]*dist[T];
        for(int t=p[T];t!=-1;t=p[e[t].u]){
            e[t].cap-=low[T];
            e[t^1].cap+=low[T];
        }
    }
    return ret;
}
int main(){
    int n,m,k;
    while(scanf("%d%d%d",&n,&m,&k),n||m||k){
        memset(pre,-1,sizeof(pre));
        cnt=0;
        T=2*n+1;S=T+1;
        memset(net,0x3f3f,sizeof(net));
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            net[u][v]=net[v][u]=min(w,net[v][u]);
        }
        rep(h,0,n)rep(i,0,n)rep(j,0,n){
            net[i][j]=min(net[i][j],net[i][h]+net[h][j]);
        }
        addedge(S,0,k,0);
        addedge(0,T,k,0);
        rep(i,1,n){
            rep(j,1,n){
                if(i<j){
                    addedge(i+n,j,1,net[i][j]);
                }
            }
            addedge(0,i,1,net[0][i]);
            addedge(i+n,T,1,net[i][0]);
            addedge(i,i+n,1,-1000000);
        }
        printf("%d\n",flowcost()+n*1000000);
    }
    return 0;
}