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;
}
评论 (0)
