本文主要是介绍HDU 4411 Arrest 最小费用最大流（题意+建图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：0代表警察局，警局里面有k个警察，然后有1~n个城市，每个城市一个小偷，要想抓到第i个城市的小偷，必须先抓或同时抓一个1~i-1城市的小偷作为铺垫，一个警察一次可以抓多个小偷，一个小偷一次被一个警察抓就可以了，抓完小偷后，必须会到警察局0点，问你所有警察走过的路程和。
想法：显然警察越少越好，先找出城市与城市之间的最短路，floyd就可以。
1.设a到b的边的容量为flow，费用为fee：a->b（flow,fee）
2.点i拆成i和i+n
虚拟一个sink和source，建边：
source->0（k，0），表示可以出动这么多的警察。
0->sink（k，0），表示有的警察可以不使用。
0->i（1，dis[0][i]）,表示警察可以走这里。
i->i+n（1，-inf），表示警察来过了这个城市，在这里有两个选择，回家或继续走下去，当然继续走下去的话，这个城市的小偷显然已经被抓住了。
i+n->kk（1，dis[i][k]），其中kk为标号大于i的城市，因为抓下面的小偷，这个走i是前提。
i+n->sink（1，dis[0][i]）,表示回家。
还有一个就是特别要注意的地方，我被坑了，这里的inf=100000就够了，这里可以试着算一下，如果过大了比如我一开始定义成了0x7fffffff（就是最大的int），应为在最短路，和流量运算的时候有的数据就已经超出了int的范围，所以就没办法完成代码，导致你找不到错误。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 100000
using namespace std;
const int edges=30000;
const int nodes=250;
int map[nodes][nodes];
int n,m,k,s,t;
int ans;
struct node
{int v,next;int flow,fee;
}e[edges];
int head[nodes],cnt;
void Init()
{memset(head,-1,sizeof(head));cnt=0;
}
void add(int a,int b,int c,int d)
{e[cnt].v=b;e[cnt].flow=c;e[cnt].fee=d;e[cnt].next=head[a];head[a]=cnt++;e[cnt].v=a;e[cnt].flow=0;e[cnt].fee=-d;e[cnt].next=head[b];head[b]=cnt++;
}
class DINIC
{public:int spath(){queue<int>q;while(!q.empty()) q.pop();for(int i=0;i<=n*2+50;i++)dis[i]=inf;memset(vis,0,sizeof(vis));memset(pe,-1,sizeof(pe));vis[s]=1;dis[s]=0;q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(dis[v]>dis[u]+e[i].fee&&e[i].flow>0){dis[v]=dis[u]+e[i].fee;pe[v]=i;if(!vis[v]){vis[v]=1;q.push(v);}}}}return dis[t]!=inf;}int Min(int a,int b){if(a<b) return a;return b;}int dfs(int u,int flow){int cost=0;if(u==t){ans+=dis[t];return flow;}for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(pe[v]==i&&e[i].flow>0){int min=dfs(v,Min(e[i].flow,flow-cost));if(min>0){e[i].flow-=min;e[i^1].flow+=min;cost+=min;if(cost==flow) break;}else pe[v]=-1;}}return cost;}void result(){while(spath()){int kk=dfs(s,inf);}}private:int dis[nodes],vis[nodes],pe[nodes];
}dinic;
void Input()
{for(int i=0;i<=n;i++)for(int j=0;j<=n;j++){if(i==j) map[i][j]=0;else map[i][j]=inf;}for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(a==b) continue;if(map[a][b]<=c) continue;map[a][b]=c;map[b][a]=c;}
}
void pretreatment()
{for(int k=0;k<=n;k++){for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){if(map[i][k]+map[k][j]<map[i][j]){map[i][j]=map[i][k]+map[k][j];}}}}
}
void build_map()
{s=2*n+1;t=2*n+2;add(s,0,k,0);add(0,t,k,0);for(int i=1;i<=n;i++){add(0,i,1,map[0][i]);add(i,i+n,1,-inf);for(int j=i+1;j<=n;j++){add(i+n,j,1,map[i][j]);}add(i+n,t,1,map[0][i]); }
}
void treatment()
{ans=0;DINIC *p=&dinic;p->result();printf("%d\n",ans+n*inf);
}
int main()
{while(~scanf("%d%d%d",&n,&m,&k),n+m+k){Init(); Input();pretreatment();build_map();treatment();}return 0;
}这篇关于HDU 4411 Arrest 最小费用最大流（题意+建图）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
