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

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

【题解】

裸上下界费用流即可。

发现以前写的费用流都有问题。。。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
*/
emodelpaper.in 说:
2023年4月21日 20:50

Board EModel Paper 2023 Aspirants who had Registered for the Board 12th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. emodelpaper.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.


登录 *


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