BZOJ 100AC啦！
我选择了这道题。
这题是一个裸的下界最小费用流
对于每条边(sa,sb)费用sc
可以连接S->sb,费用sc容量1表示至少走一次
sa->sb,费用sc,容量INF表示可以走多次
对于每个点i
可以连接i->T费用0容量nk表示可以从这里离开(此时已经看完了全部剧情)
i->1费用0容量INF表示可以在i号点退出游戏重新开始一局新游戏
看不懂请看代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | #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)
