[POI 19 Stage 3] Minimalist Security

作法：

首先可以發現，如果一個點的點權確定了，那麼那個點所在的連通快的全部點權也就確定了，所以可以對每個連通塊分開作，再全部加起來得到答案。對於一個連通塊，如果有奇圈的話，那麼會得到所有奇圈上的點的權重都確定了( 想像一下沿路加減加減，最後得到的值會是兩倍的某點點權 )，當然如果加減得到的值是奇數就是無解。在這種情況下，因為已經確定一個點了，所以可以直接 DFS 求出其他所有點的點權，並加到答案裡，而如果在 DFS 的過程中出現矛盾( 這個點的點權太大或太小 ) 那就趕快回 return false 。而如果沒有奇圈只有偶圈的話，因為偶圈必須要滿足沿著圈走加減加減最後會得到0，這也就代表隨便對某一個點賦一個值的話，合法的偶圈可以保證走完一圈更新完點權之後不會矛盾，而不合法的則沒辦法保證，所以只要在DFS的過程中沿路確定點權，如果遇到一個點和自己形成偶圈，並且點權產生矛盾，那就代表無解。

如果把隨便一個點賦值之後在DFS的過程中沒有出現任何矛盾，那麼如果考慮把這個點的點權加上 t ，那麼會得到其他所有點要嘛會 +t ，要嘛會 -t ，而這就等價於每個點是落在這張二部圖的哪個部分(因為此時沒有奇圈)，所以我們可以算出 t 的範圍，並且因為所有點的點權都是一次函數，而我們要maximize / minimize 的數也是對 t 的一次函數，所以我們只要考慮 t 最大和 t 最小的情形即可。如果求出的 t 的範圍會導致 t 不存在，那也代表無解，否則對最小的 t 和最大的 t 代入點權分別進行一次DFS求答案，就可以得到最大和最小所求值了。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF (1LL<<60)
using namespace std;
const int maxn=500000+10 ;
 
struct P{int to,d;};
 
vector<P> v[maxn] ;
int num[maxn],vis[maxn],col[maxn] ;
LL val[maxn] ;
 
int tmp[maxn],cnt ;
void dfs0(int x)
{
    vis[x]=1 ; tmp[cnt++]=x ;
    for(int i=0;i<v[x].size();i++) if(!vis[v[x][i].to])
        dfs0(v[x][i].to) ;
}
 
int fa[maxn],fa_d[maxn] ;
int dfs1(int x,int c)
{
    col[x]=c ;
    for(int i=0;i<v[x].size();i++) if(v[x][i].to!=fa[x])
    {
        if(col[v[x][i].to]==-1)
        {
            val[v[x][i].to]=v[x][i].d-val[x] ;
            fa[v[x][i].to]=x ; fa_d[v[x][i].to]=v[x][i].d ;
 
            int res=dfs1(v[x][i].to,c^1) ;
            if(res!=0) return res ;
        }
        else if(col[v[x][i].to]!=c)
        {
            if(val[v[x][i].to]+val[x]!=v[x][i].d) return -1 ;
        }
        else
        {
            LL sum=v[x][i].d + fa_d[x] ;
            for(int j=fa[x],k=-1;j!=v[x][i].to;j=fa[j])
                sum+= k*fa_d[j] , k=-k ;
            if(sum%2) return -1 ;
            val[x]=sum/2 ; return x ;
        }
    }
    return 0 ;
}
 
int dfs2_cnt ;
bool dfs2(int x,LL &sum)
{
    if(val[x]<0 || val[x]>num[x]) return 0 ;
    else sum+=num[x]-val[x] ;
    vis[x]=dfs2_cnt ;
    for(int i=0;i<v[x].size();i++)
    {
        if(vis[v[x][i].to]==dfs2_cnt)
        {
            if(val[v[x][i].to]+val[x]!=v[x][i].d) return 0 ;
        }
        else
        {
            val[v[x][i].to]=v[x][i].d-val[x] ;
            if(!dfs2(v[x][i].to,sum)) return 0 ;
        }
    }
    return 1 ;
}
 
bool solve(int x,LL &mi,LL &ma)
{
    cnt=0 ; dfs0(x) ;
 
    val[x]=0 ; fa[x]=x ;
    int res=dfs1(x,0) ;
    if(res==-1) return 0 ;
    else if(res>0)
    {
        mi=ma=0LL ; dfs2_cnt=2 ;
        if(!dfs2(res,mi)) return 0 ;
        ma=mi ; return 1 ;
    }
 
    LL tmi=-INF , tma=INF ;
    for(int i=0;i<cnt;i++)
    {
        if(col[tmp[i]]==0)
            tmi=max(tmi,-val[tmp[i]]) ,
            tma=min(tma,-val[tmp[i]]+num[tmp[i]]) ;
        else
            tmi=max(tmi,val[tmp[i]]-num[tmp[i]]) ,
            tma=min(tma,val[tmp[i]]) ;
    }
    if(tmi > tma) return 0 ;
    val[tmp[0]]+= ( col[tmp[0]]==0 ? tmi : -tmi ) ;
    dfs2_cnt=2 ; mi=0LL ; dfs2(tmp[0],mi) ;
    val[tmp[0]]-= ( col[tmp[0]]==0 ? tmi : -tmi ) ;
    val[tmp[0]]+= ( col[tmp[0]]==0 ? tma : -tma ) ;
    dfs2_cnt=3 ; ma=0LL ; dfs2(tmp[0],ma) ;
    if(mi>ma) swap(mi,ma) ;
    return 1 ;
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) scanf("%d",&num[i]) ;
    while(m--)
    {
        int x,y,d ; scanf("%d%d%d",&x,&y,&d) ;
        v[x].push_back((P){y,d}) ;
        v[y].push_back((P){x,d}) ;
    }
 
    memset(col,-1,sizeof(col)) ;
    LL ans1=0LL , ans2=0LL ;
    for(int i=1;i<=n;i++) if(!vis[i])
    {
        LL mi,ma ;
        if(!solve(i,mi,ma)) { printf("NIE\n") ; return 0 ; }
        ans1+=mi ; ans2+=ma ;
    }
    printf("%lld %lld\n",ans1,ans2) ;
}