【JZOJ6229】【20190621】san

题目

$n$个点$m$条边的有向图，每个点有点权

你可以选择拓扑序的一个区间的

最大化点权和

$n \le 50 \ , m \le \frac{n*(n-1)}{2} , 0 \le |a_i| \le 200 $

题解

一条路径上的点一定是：不选-选-不选
把所有正权加起来为sum，然后建最小割模型，割哪段表示选在
连边：

$ (w_i \gt 0) (S,i,w_i) \ (i',T,w_i) $

$ (w_i \lt 0) (i,i',-w_i) $
边有向边$(a,b)$相当于限制了a割的段不能在b后面

那连边：

$(a,b,inf) \ , \ (a',b',inf)$
答案是sum-flow

#include<bits/stdc++.h>

#define inf 0x3f3f3f3f

using namespace std;

const int N=110;

int n,m,vis[N],cur[N],hd[N],o,S,T,d[N];

struct Edge{int v,nt,f;}E[N*N];

int q[N],head,tail;

void adde(int u,int v,int f){

	E[o]=(Edge){v,hd[u],f};hd[u]=o++;

	E[o]=(Edge){u,hd[v],0};hd[v]=o++;

}

bool bfs(){

	for(int i=S;i<=T;++i)vis[i]=0,d[i]=0;

	head=tail=0;vis[q[++tail]=S]=1;d[S]=1;

	while(head<tail){

		int u=q[++head];

		for(int i=hd[u];~i;i=E[i].nt)if(E[i].f){

			int v=E[i].v;

			if(vis[v])continue;

			vis[v]=1;

			d[v]=d[u]+1;

			q[++tail]=v;

			if(v==T)return true;

		}

	}return false;

}

int dfs(int u,int F){

	if(u==T||!F)return F;

	int flow=0,f;

	for(int i=cur[u];~i;i=E[i].nt){

		int v=E[cur[u]=i].v;

		if(d[v]==d[u]+1&&(f=dfs(v,min(F,E[i].f)))){

			flow+=f,F-=f;

			E[i].f-=f,E[i^1].f+=f;

			if(!F)break;

		}

	}

	if(!flow)d[u]=0;//记得加上这条优化

	return flow;

}

int main(){

	freopen("san.in","r",stdin);

	freopen("san.out","w",stdout);

	scanf("%d%d",&n,&m);

	int ans=0;S=0;T=n*2+1;

	for(int i=S;i<=T;++i)hd[i]=-1;

	for(int i=1,w;i<=n;++i){

		scanf("%d",&w);

		if(w>0)ans+=w,adde(S,i,w),adde(i+n,T,w);

		else adde(i,i+n,-w);

	}

	for(int i=1,u,v;i<=m;++i){

		scanf("%d%d",&u,&v);

		adde(u,v,inf);

		adde(u+n,v+n,inf);

	}

	while(bfs()){

		for(int i=S;i<=T;++i)cur[i]=hd[i];

		ans-=dfs(S,inf);

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

【JZOJ6229】【20190621】san

题目

题解

最新文章

热门文章