题目链接：

题意：有n+1个城市，编号0到n。其中警察局在0号城市，1到n号城市中每个城市都有一个小偷。现在警察局里有K个警察。现在让这K个警察去抓小偷（当然抓一个小偷只需要一个警察就行了。。）。

（1）每两个城市之间有距离；

（2）在抓i城市的小偷的时候i-1城市的小偷必须先抓住；

（3）所有警察（也可能用不到K个警察）在抓完小偷后都要返回警察局。

求出所有警察抓小偷所走的路程和

思路：拆点i和i+n(1<=i<=n)。

（1）i+n到j(i<j)连边容量为1，费用为i到j的最短路（抓完i城市的小偷接着去抓j城市的小偷）；

（2）0到i，容量为1，费用g[0][i]（去抓i城市的小偷）；

（3）i+n到汇点，容量为1，费用为g[0][i]（回到警察局）；

（4）i到i+n,容量为1，费用为负无穷，这样就保证肯定这个城市必被访问到；

（5）源点到0，容量为K，费用为0（有K个警察可用）；

（6）在0和汇点连容量为K费用为0的边(有的人可以一直呆在警察局里。。。)

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))using namespace std;struct node{    int u,v,cost,flow,next;};const int INF=1000000;node edges[1000005];int head[205],e;int pre[205],in[205],cost[205],flow[205];int s,t;queue
         
           Q;int g[105][105],n,m,K;void add(int u,int v,int flow,int cost){    edges[e].u=u;    edges[e].v=v;    edges[e].cost=cost;    edges[e].flow=flow;    edges[e].next=head[u];    head[u]=e++;}void Add(int u,int v,int flow,int cost){    add(u,v,flow,cost);    add(v,u,0,-cost);}int SPFA(int s,int t){    int i,u,v;    memset(pre,-1,sizeof(pre));    memset(flow,0,sizeof(flow));    memset(in,0,sizeof(in));    for(i=0;i<=t;i++) cost[i]=INF;    while(!Q.empty()) Q.pop();    Q.push(s);    in[s]=1;    flow[s]=INF;    cost[s]=0;    while(!Q.empty())    {        u=Q.front();        Q.pop();        in[u]=0;        for(i=head[u];i!=-1;i=edges[i].next)        {            v=edges[i].v;            if(edges[i].flow>0&&cost[v]>cost[u]+edges[i].cost)            {                cost[v]=cost[u]+edges[i].cost;                pre[v]=i;                flow[v]=min(flow[u],edges[i].flow);                if(!in[v])                {                    in[v]=1;                    Q.push(v);                }            }        }    }    return flow[t];}int MCMF(int s,int t){    int mincost=0,minflow,i;    while(minflow=SPFA(s,t))    {        for(i=pre[t];i!=-1;i=pre[edges[i].u])        {            mincost+=minflow*edges[i].cost;            edges[i].flow-=minflow;            edges[i^1].flow+=minflow;        }    }    return mincost;}void init(){    memset(head,-1,sizeof(head));    e=0;    s=n+n+1;    t=s+1;    int i,j;    Add(s,0,K,0);    Add(0,t,K,0);    for(i=1;i<=n;i++)    {        Add(i,i+n,1,-INF);        if(g[0][i]