[AHOI2014/JSOI2014]支线剧情

题目

有源汇上下界最小费用可行流

首先注意到要求是每一条边都经过至少一次，所以对于每一条边我们设成\([1,\infty]\)就好了

另外所有点都能结束剧情，所有点都要向汇点\(t\)连一条\([0,\infty]\)的边

我们根据有源汇可行流的方式建图就好了

定义\(d_i\)为流入这个点的所有边的下界和减去流出这个点的所有边的下界和

对于图中的一条边\((u,v,[b,c],w)\)，我们连一条从\(u\)到\(v\)流量为\(c-b\)费用为\(w\)的边

我们再从汇点向源点连一条容量为\(\infty\)费用为\(0\)的边

对于\(d_i>0\)的点，我们从超级源点\(S\)向这个点连一条容量为\(d_i\)费用为\(0\)的边

对于\(d_i<0\)的点，我们让这个点向超级汇点连一条容量为\(-d_i\)费用为\(0\)的边

我们在这张图上跑一个最小费用最大流就好了

最后别忘了把答案加上原图里所有边的流量下界乘以费用的和

代码

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int maxn=705;

std::queue<int> q;

const int inf=999999999;

struct E{int v,nxt,w,f;}e[50005];

int head[maxn],in[maxn],out[maxn],r[maxn],d[maxn],vis[maxn];

int n,num=1,S,T,ans;

inline void C(int x,int y,int f,int w) {

	e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=w;e[num].f=f;

}

inline void add(int x,int y,int f,int w) {C(x,y,f,w),C(y,x,0,-1*w);}

inline int SPFA() {

	for(re int i=S;i<=T;i++) d[i]=inf,vis[i]=0;

	d[T]=0,q.push(T);

	while(!q.empty()) {

		int k=q.front();q.pop();vis[k]=0;

		for(re int i=head[k];i;i=e[i].nxt)

		if(e[i^1].f&&d[e[i].v]>d[k]+e[i^1].w) {

			d[e[i].v]=d[k]+e[i^1].w;

			if(!vis[e[i].v]) vis[e[i].v]=1,q.push(e[i].v);

		}

	}

	return d[S]<inf;

}

int dfs(int x,int now) {

	if(x==T||!now) return now;

	int flow=0,ff;vis[x]=1;

	for(re int i=head[x];i;i=e[i].nxt)

	if(e[i].f&&!vis[e[i].v]&&d[e[i].v]==d[x]+e[i^1].w) {

		ff=dfs(e[i].v,min(e[i].f,now));

		if(ff<=0) continue;

		now-=ff,flow+=ff,e[i].f-=ff,e[i^1].f+=ff;

		if(!now) break;

	}

	return flow;

}

inline int zkw() {

	while(SPFA()) {

		vis[T]=1;

		while(vis[T]) {

			for(re int i=S;i<=T;i++) vis[i]=0;

			ans+=dfs(S,inf)*d[S];

		}

	}

	return ans;

}

int main() {

	n=read();T=n+1;

	int ki,vi,ti;

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

		ki=read();

		for(re int j=1;j<=ki;j++) {

			vi=read(),ti=read();

			add(i,vi,inf-1,ti);ans+=ti;

			r[i]--,r[vi]++;

		}

		add(i,T,inf,0);

	}

	add(T,1,inf,0);++T;

	for(re int i=1;i<T;i++) {

		if(r[i]==0) continue;

		if(r[i]>0) add(S,i,r[i],0);

			else add(i,T,-1*r[i],0);

	}

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

	return 0;

}

巴特西

[AHOI2014/JSOI2014]支线剧情

最新文章

热门文章