本文共 1910 字，大约阅读时间需要 6 分钟。
题解：最大权闭合子图。将正向收益与S连，花费与T连。建立用户到他后继中转站容量为INF的边，保证不会被割。最后正向收益的和减去最小割就是答案。
#include #include #include #include #include #include #include #include #include #include #include //CLOCKS_PER_SEC#define se second#define fi first#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define Pii pair #define Pli pair #define ull unsigned long long#define pb push_back#define fio ios::sync_with_stdio(false);cin.tie(0)const double Pi=3.14159265;const int N=4e6+10;const ull base=163;const int INF=0x3f3f3f3f;using namespace std;int head[100000],to[N],tot=0,nx[N],cap[N];int s,t;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}void add(int u,int v,int c){ to[tot]=v; nx[tot]=head[u]; cap[tot]=c; head[u]=tot++; to[tot]=u; nx[tot]=head[v]; cap[tot]=0; head[v]=tot++;}int d[100000];int cur[100000];int bfs(){ memset(d,-1,sizeof(d)); queue q; q.push(s); d[s]=1; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];~i;i=nx[i]){ int v=to[i]; if(d[v]==-1&&cap[i]>0){ d[v]=d[u]+1; q.push(v); } } } return d[t]!=-1;}int dfs(int s,int a){ if(s==t||a==0)return a; int flow=0,f; for(int &i=cur[s];~i;i=nx[i]){ int v=to[i]; if(d[s]+1==d[v] && cap[i]>0 && (f=dfs(v,min(a,cap[i])))>0){ flow+=f; cap[i]-=f; cap[i^1]+=f; a-=f; if(a==0)break; } } return flow;}int dinic(){ int ans=0; while(bfs()){ for(int i=0;i<=t;i++)cur[i]=head[i]; while(int di=dfs(s,INF)){ ans+=di; } } return ans;}int p[N];int main(){ int n,m; n=read(),m=read(); memset(head,-1,sizeof(head)); s=0,t=60000; for(int i=1;i<=n;i++){ p[i]=read(); add(i,t,p[i]); } int o=n+1; int sum=0; while(m--){ int l,r,c; l=read(),r=read(),c=read(); sum+=c; add(s,o,c); add(o,l,INF); add(o,r,INF); o++; } cout<
转载于:https://www.cnblogs.com/Mrleon/p/9142619.html