BZOJ 3876 [Ahoi2014] 支线剧情 【带上下界网络流】

tonyfang posted @ 2016年3月05日 15:38 in BZOJ with tags C++ OI , 156 阅读

【题解】

裸上下界费用流即可。

发现以前写的费用流都有问题。。。gg

 

# include <stdio.h>
# include <string.h>
# include <queue> 
using namespace std;

const int M=1000010,Me=1010;
int tot=1,head[Me],next[M],to[M],flow[M],w[M],S,T,pre[Me],d[Me],from[Me];
bool vis[Me];
const int INF=0x3f3f3f3f;

inline void add(int u,int v,int fl,int ws) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	flow[tot]=fl;
	w[tot]=ws;
}
inline void Add(int u,int v,int fl,int ws) {
	add(u,v,fl,ws);
	add(v,u,0,-ws);
}

int ans=0;
inline bool spfa() {
	queue<int> q;
    while(!q.empty()) q.pop();
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    d[S]=0; vis[S]=1; q.push(S);
    while(!q.empty()) {
        int top=q.front(); q.pop();
        vis[top]=0;
        for (int i=head[top];i;i=next[i]) {
            if(d[top]+w[i]<d[to[i]]&&flow[i]) {
                d[to[i]]=d[top]+w[i];
                if(!vis[to[i]]) {
                    vis[to[i]]=1;
                    q.push(to[i]);
                }
                pre[to[i]]=i;
            	from[to[i]]=top;
	    }
        }
    }
    return d[T]!=INF;
}
inline void mcf() {
    int xm=1e9;
    for (int i=T;i!=S;i=from[i])
    	xm=min(xm,flow[pre[i]]);
    for (int i=T;i!=S;i=from[i]) {
        flow[pre[i]]-=xm;
        flow[pre[i]^1]+=xm;
    }
    ans=ans+d[T]*xm;
}

inline long long g() {
	while(spfa()) mcf();
}

int n;

int main() {
	scanf("%d",&n);
	S=0,T=Me-1;
	for (int i=1,b,Te,t;i<=n;++i) {
		scanf("%d",&Te);
		Add(i,1,INF,0);
		for (int j=1;j<=Te;++j) {
			scanf("%d%d",&b,&t);
			Add(i,b,INF,t);
			Add(S,b,1,t);
			Add(i,T,1,0);
		}
	}
	g();
	printf("%d\n",ans);
	return 0;
}
/*
6
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0 
0 
0
*/

登录 *


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