小饭桌 2018-03-07
设$degi[x]$和$dego[x]$分别表示每个点的入度和出度,将线性规划的限制写出来:
目标函数:
$\max.\ \sum_{x=1}^n(dego[x]P[x]-degi[x]Q[x])$
限制:
$P[x]-Q[y]\leq T(x,y)-L(x,y)$
$Q[y]-P[x]\leq L(x,y)-S(x,y)$
$P[x]\leq 10^6$
$Q[x]\leq 10^6$
这是个标准型线性规划,将其对偶,得到每条边的两个辅助变量$a,b$以及每个$P,Q$对应上界的辅助变量$c,d$:
目标函数:
$\min.\ \sum_{(x,y)\in E}((T(x,y)-L(x,y))a(x,y)+(L(x,y)-S(x,y))b(x,y))+\sum_{x=1}^n(10^6c[x]+10^6d[x])$
限制:
$\sum_{(x,i)\in E}a(x,i)-\sum_{(i,x)\in E}b(i,x)+c[x]\geq dego[x]$
$\sum_{(i,x)\in E}b(i,x)-\sum_{(x,i)\in E}a(x,i)+d[x]\geq -degi[x]$
将每条限制看作点,每个二元变量看作边,在对应负系数限制连向正系数限制,流量$[0,+\infty)$,费用为在目标函数中的系数。
对于$c$和$d$,从$S$向$x$连边,流量$[0,+\infty)$,费用$10^6$。
对于$dego[x]$,从$x$向$T$连边,流量$[dego[x],+\infty)$,费用$0$。
对于$-degi[x]$,从$S$向$x$连边,流量$[degi[x],degi[x]]$,再从$x$向$T$连边,流量$[0,+\infty)$,费用$0$。
则答案就是这个图的最小费用可行流,当出现负环时该线性规划无界,故原问题无解。
#include<cstdio> typedef long long ll; const int N=60010,M=1000000; const ll inf=1LL<<60; int Case,n,m,i,degi[N],dego[N];ll tmp,ans; int u[M],v[M],nxt[M],t,S,T,SS,TT,q[M],g[N],f[N],cnt[N];ll c[M],co[M],d[N],in[N];bool vis[N]; unsigned short l,r; inline void add(int x,int y,ll l,ll r,ll z){ r-=l,in[x]-=l,in[y]+=l; if(!r)return; u[++t]=x;v[t]=y;c[t]=r;co[t]=z;nxt[t]=g[x];g[x]=t; u[++t]=y;v[t]=x;c[t]=0;co[t]=-z;nxt[t]=g[y];g[y]=t; } int spfa(){ int x,i; for(i=1;i<=TT;i++)d[i]=inf,vis[i]=cnt[i]=0; d[SS]=0;vis[SS]=1;q[l=r=0]=SS; while(l!=r+1){ x=q[l++]; if(x==TT)continue; vis[x]=0; for(i=g[x];i;i=nxt[i])if(c[i]&&co[i]+d[x]<d[v[i]]){ d[v[i]]=co[i]+d[x];f[v[i]]=i; if(!vis[v[i]]){ vis[v[i]]=1; cnt[v[i]]++; if(cnt[v[i]]>TT+5)return -1; q[++r]=v[i]; } } } return d[TT]<inf; } bool solve(){ scanf("%d%d",&n,&m); S=n*2+1; T=S+1; SS=T+1; TT=SS+1; for(t=i=1;i<=TT;i++)degi[i]=dego[i]=g[i]=in[i]=0; ans=0; add(T,S,0,inf,0); bool flag=0; while(m--){ int x,y,_L,_S,_T; scanf("%d%d%d%d%d",&x,&y,&_L,&_S,&_T); if(_S>_T)flag=1; dego[x]++; degi[y]++; ans+=_L; add(y+n,x,0,inf,_T-_L); add(x,y+n,0,inf,_L-_S); } if(flag)return 0; for(i=1;i<=n;i++){ add(S,i,0,inf,1000000); add(i,T,dego[i],inf,0); add(S,i+n,0,inf,1000000); add(S,i+n,degi[i],degi[i],0); add(i+n,T,0,inf,0); } for(i=1;i<=TT;i++){ if(in[i]>0)add(SS,i,0,in[i],0); if(in[i]<0)add(i,TT,0,-in[i],0); } while(1){ int o=spfa(); if(!o)return 1; if(o==-1)return 0; for(tmp=inf,i=TT;i!=SS;i=u[f[i]])if(tmp>c[f[i]])tmp=c[f[i]]; for(ans+=d[i=TT]*tmp;i!=SS;i=u[f[i]])c[f[i]]-=tmp,c[f[i]^1]+=tmp; } } int main(){ scanf("%d",&Case); while(Case--)if(!solve())puts("Unlike");else printf("%lld\n",ans); return 0; }