【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
#define inf 0x3f3f3f3fusing 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(head0)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< 转载于:https://www.cnblogs.com/Paul-Guderian/p/11074208.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！