3
22
2016
0

[BZOJ3876] [Ahoi2014]支线剧情

BZOJ 100AC啦!

我选择了这道题。

这题是一个裸的下界最小费用流

对于每条边(sa,sb)费用sc

可以连接S->sb,费用sc容量1表示至少走一次

sa->sb,费用sc,容量INF表示可以走多次

对于每个点i

可以连接i->T费用0容量nk表示可以从这里离开(此时已经看完了全部剧情)

i->1费用0容量INF表示可以在i号点退出游戏重新开始一局新游戏

看不懂请看代码

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

int n,en,S,T,link[2005],h[2005],D[2005],flag[2005];

struct Edge{
int b,c,f,back,next;
}e[1000005];

void AddEdge(int sa,int sb,int sc,int sd){
e[++en].b=sb;
e[en].f=sc;
e[en].c=sd;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].c=-sd;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int SPFA(){
queue<int> Q;
memset(D,127,sizeof(D));
Q.push(S);
D[S]=0;
flag[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	flag[u]=0;
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(e[i].f && D[v]>D[u]+e[i].c){
			D[v]=D[u]+e[i].c;
			link[v]=i;
			if(!flag[v]){
				flag[v]=1;
				Q.push(v);
			}
		}
	}
}
return D[T]<2000000000;
}

int Cost(){
int Tow=link[T],flow=2100000000,cost=0;
while(Tow!=link[S]){
	flow=min(flow,e[Tow].f);
	Tow=link[e[e[Tow].back].b];
}
Tow=link[T];
while(Tow!=link[S]){
    e[Tow].f-=flow;
    e[e[Tow].back].f+=flow;
    cost+=flow*e[Tow].c;
    Tow=link[e[e[Tow].back].b];
}
return cost;
}

int Flow(){
int ans=0;
while(SPFA())ans+=Cost();
return ans;
}

int main(){
freopen("3876.in","r",stdin);
freopen("3876.out","w",stdout);
scanf("%d",&n);
S=n+1;T=n+2;
for(int i=1;i<=n;i++){
	int nk;
	scanf("%d",&nk);
	for(int j=1;j<=nk;j++){
		int sa,sb;
		scanf("%d %d",&sa,&sb);
		AddEdge(S,sa,1,sb);
		AddEdge(i,sa,2100000000,sb);
	}
	AddEdge(i,T,nk,0);
	if(i!=1)AddEdge(i,1,2100000000,0);
}
printf("%d\n",Flow());
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 497

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com