裸的上下界費用流。。。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<bitset>
#include<sstream>
#include<cstdlib>
#define QAQ int
#define TAT long long
#define OwO bool
#define ORZ double
#define Ug unsigned
#define F(i,j,n) for(QAQ i=j;i<=n;++i)
#define E(i,j,n) for(QAQ i=j;i>=n;--i)
#define MES(i,j) memset(i,j,sizeof(i))
#define MEC(i,j) memcpy(i,j,sizeof(j))
using namespace std;
const QAQ N=505,M=5000000;
const QAQ oo=1e8;
QAQ n,m,s,t;
struct Link{
QAQ to,last,rem,val,from;
}a[M];
QAQ head[N],js=1,ans;
QAQ dis[N];
OwO vis[N];
queue<QAQ> q;
void add(QAQ x,QAQ y,QAQ z,QAQ w){
a[++js].from=x;a[js].to=y;
a[js].rem=z;a[js].val=w;
a[js].last=head[x];head[x]=js;
}
void Insert(QAQ x,QAQ y,QAQ z,QAQ w){
add(x,y,z,w);add(y,x,0,-w);
}
OwO spfa(QAQ s,QAQ t){
F(i,s,t) dis[i]=oo,vis[i]=0;
dis[t]=0;vis[t]=1;
q.push(t);
while(!q.empty()){
QAQ x=q.front();q.pop();vis[x]=0;
for(QAQ i=head[x];i;i=a[i].last) if(a[i^1].rem&&dis[a[i].to]>dis[x]-a[i].val){
dis[a[i].to]=dis[x]-a[i].val;
if(!vis[a[i].to]) vis[a[i].to]=1,q.push(a[i].to);
}
}
return dis[s]<oo;
}
QAQ dfs(QAQ x,QAQ want){
if(x==t||!want) {
// vis[x]=1;
return want;
}
QAQ f=0;
vis[x]=1;
for(QAQ i=head[x];i;i=a[i].last) if(!vis[a[i].to]&&a[i].rem&&dis[a[i].to]==dis[x]-a[i].val){
QAQ d=dfs(a[i].to,min(want-f,a[i].rem));
if(d){
ans+=d*a[i].val;
a[i].rem-=d;
a[i^1].rem+=d;
f+=d;
}
if(f==want) break;
}
vis[x]=0;
return f;
}
void zkw(){
// QAQ ans=0;
while(spfa(s,t)){
vis[t]=1;
while(vis[t]){
MES(vis,0);
dfs(s,oo);
}
}
// return ans;
}
QAQ main(){
scanf("%d",&n);
s=0;t=n+1;
F(i,1,n){
QAQ k;
scanf("%d",&k);
if(k) Insert(i,t,k,0);
if(i!=1) Insert(i,1,oo,0);
while(k--){
QAQ v,w;
scanf("%d%d",&v,&w);
Insert(s,v,1,w);
Insert(i,v,oo,w);
}
}
zkw();
printf("%d
",ans);
return 0;
}
View Code