题解 P3872 【[TJOI2010]电影迷】

· · 题解 

    S 向正权点建边，容量为点权；负权点向 T 建边，容量为点权绝对值，

    x->y 的限制就直接建 x->y。最后拿正权和-最小割就是答案。

这是神仙出题人的方法，我来给一个完整的正确性证明。

证明

若一个限制条件连的 x, y 点权不同号，在取了其中正的那个后，要么放弃正的，要么取了负的，要么减少 dXY，与连边方式的最小割相同。

如果同号会怎样呢？

我们任意选两个同号点1, 2，连边2->1，选1的任意一条到T的路径1->3->T。（如果没有这条路径那么1，2常规都选（负点权则不选）答案不受影响）

边a, x, y中至少有一条删掉。

1. 删x或y：

1，2仍然都选，且不用割去其它边，答案不受影响。

2. 删a：

1不选了，这时要么不选2（割b）要么损失d12（割c）。

如果割x或y了咋办？

怎么可能，那样转化为上一种情况，a就不用割了，不是最小割。

那这样答案也不受影响了。

综上

同号的限制条件也解决了。

证毕

最后还是贴一下代码吧。

//coder: Feliks*GM-YB
#include<bits/stdc++.h>
#define fu(i,a,b) for(register int i = a, I = (b) + 1; i < I; ++i)
#define fd(i,a,b) for(register int i = a, I = (b) - 1; i > I; --i)
typedef long long ll;
using namespace std;
template <class T> inline void read(T &x) {
    x=0;T f=1;char ch=getchar();
    while(!isdigit(ch))f=ch=='-'?-1:1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    x*=f;
}int n,m;
#define go(x) for(int i=first[x],y=v[i];i;i=nex[i],y=v[i])
const int N=1e3+5;
const int M=1e5+5;
int v[M],nex[M],w[M],first[N],tot=1;
inline void add(int x,int y,int z){
    v[++tot]=y;w[tot]=z;
    nex[tot]=first[x];
    first[x]=tot;
}namespace Dinic{
    const int s=0;
    const int t=N-4;
    const int inf=1e9+7;
    int d[N],flow,ans;
    queue<int> q;
    inline bool bfs(){
        while(!q.empty())q.pop();
        memset(d,0,sizeof(d));
        q.push(s);d[s]=1;
        while(!q.empty()){
            int x=q.front();q.pop();
            go(x){
                if(!w[i] || d[y])continue;
                q.push(y);
                d[y]=d[x]+1;
                if(y==t)return 1;
            }
        }return 0;
    }int dinic(int x,int f){
        if(x==t)return f;
        int res=f,k;
        for(int i=first[x],y=v[i];i && res;i=nex[i],y=v[i]){
            if(!w[i] || d[y]!=d[x]+1)continue;
            k=dinic(y,min(res,w[i]));
            if(!k)d[y]=0;
            w[i]-=k;w[i^1]+=k;
            res-=k;
        }return f-res;
    }inline void solve(int c){
        while(bfs()){
            while(flow=dinic(s,inf))ans+=c*flow;
        }
    }
}using namespace Dinic;
int a[N],df;
int main(){
    read(n),read(m);
    fu(i,1,n){
        read(a[i]);
        if(a[i]>=0)add(s,i,a[i]),add(i,s,0),ans+=a[i];
        else add(i,t,-a[i]),add(t,i,0);
    }fu(i,1,m){
        int x,y;
        read(x),read(y);
        read(df);
        add(x,y,df),add(y,x,0);
    }solve(-1);
    printf("%d\n",ans);
    return 0;
}