BZOJ 2324: [ZJOI2011]营救皮卡丘(带上下限的最小费用最大流)

这道题么= =还是有些恶心的，第一次写带上下界的网络流，整个人都萌萌哒~~~

首先先预处理得最短路后

直接用费用流做就行了。

第一次写，还是挺好写的= =

CODE：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

#define maxn 310

#define maxm 100000

struct edges{

int to,next,cap,dist;

}edge[maxm];

int next[maxn],l;

void addedge(int x,int y,int z,int d){

l++;

edge[l*2]=(edges){y,next[x],z,d};next[x]=l*2;

edge[l*2+1]=(edges){x,next[y],0,-d};next[y]=l*2+1;

}

int inf;

int dist[maxn],w[maxn],s,t,cnt;

bool b[maxn];

queue<int> q;

bool spfa() {

for (int i=1;i<=cnt;i++) dist[i]=inf;

dist[s]=0;

q.push(s);

while (!q.empty()) {

int u=q.front();q.pop();

b[u]=0;

for (int i=next[u];i;i=edge[i].next)

if (edge[i].cap&&edge[i].dist+dist[u]<dist[edge[i].to]) {

dist[edge[i].to]=dist[u]+edge[i].dist;

w[edge[i].to]=i;

if (!b[edge[i].to]) {

b[edge[i].to]=1;

q.push(edge[i].to);

}

return dist[t]!=inf;

}

int ans;

int mcmf(int ss,int tt){

s=ss,t=tt;

while (spfa()) {

int x=t,flow=inf;

while (x!=s) {

flow=min(flow,edge[w[x]].cap);

x=edge[w[x]^1].to;

}

ans+=flow*dist[t];

x=t;

while (x!=s) {

edge[w[x]].cap-=flow;

edge[w[x]^1].cap+=flow;

x=edge[w[x]^1].to;

}

int dis[maxn][maxn],f[maxn][maxn],id[maxn][2];

int main(){

int n,m,k;

scanf("%d%d%d",&n,&m,&k);

memset(f,10,sizeof(f));

inf=f[0][0];

for (int i=1;i<=m;i++) {

int x,y,z;

scanf("%d%d%d",&x,&y,&z);

f[x][y]=f[y][x]=min(f[x][y],z);

}

for (int i=0;i<=n;i++) f[i][i]=0;

for (int k=0;k<=n;k++) {

for (int i=0;i<=n;i++)

for (int j=0;j<=n;j++)

f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

for (int i=0;i<=n;i++) dis[i][k]=f[i][k];

}

for (int i=0;i<=n;i++) id[i][0]=++cnt;

for (int i=0;i<=n;i++) id[i][1]=++cnt;

int s=++cnt,t=++cnt;

addedge(id[0][0],id[0][1],k,0);

for (int i=1;i<=n;i++) {

addedge(id[0][1],id[i][0],inf,dis[0][i]);

addedge(id[i][1],id[n][1],inf,0);

addedge(id[i][0],id[i][1],inf,0);

addedge(s,id[i][1],1,0);

addedge(id[i][0],t,1,0);

}

for (int i=0;i<n;i++)

for (int j=i+1;j<=n;j++)

if (dis[i][j]!=inf) addedge(id[i][1],id[j][0],inf,dis[i][j]);

addedge(id[n][1],id[0][0],inf,0);

mcmf(s,t);

next[s]=next[t]=0;

next[id[n][1]]=edge[next[id[n][1]]].next;

next[id[0][0]]=edge[next[id[0][0]]].next;

mcmf(id[0][0],id[n][1]);

printf("%d\n",ans);

return 0;

}

巴特西

BZOJ 2324: [ZJOI2011]营救皮卡丘(带上下限的最小费用最大流)

最新文章

热门文章