[JSOI2009] 球队收益 （费用流）

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<queue>#include<climits>using namespace std;inline int read(){ ???int f=1,ans=0;char c=getchar(); ???while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} ???while(c>=‘0‘&&c<=‘9‘){ans=ans*10+c-‘0‘;c=getchar();} ???return f*ans;}queue<int> que;const int MAXN=400001;struct node{ ???int u,v,w,cost,nex;}x[MAXN];int head[MAXN],dis[MAXN],vis[MAXN],S,T,cnt,cost,INF=INT_MAX;void add(int u,int v,int cost,int w){// ???printf("u:%d v:%d cost:%d w:%d\n",u,v,cost,w); ???x[cnt].u=u,x[cnt].v=v,x[cnt].cost=cost,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++;swap(u,v);w=0,cost=-cost; ???x[cnt].u=u,x[cnt].v=v,x[cnt].cost=cost,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++;} bool spfa(){ ???memset(vis,0,sizeof(vis));memset(dis,127/3,sizeof(dis));int inf=dis[0];dis[S]=0; ???que.push(S); ???while(!que.empty()){ ???????int xx=que.front();que.pop(); ???????for(int i=head[xx];i!=-1;i=x[i].nex){ ???????????if(dis[x[i].v]>dis[xx]+x[i].cost&&x[i].w){ ???????????????dis[x[i].v]=dis[xx]+x[i].cost; ???????????????if(!vis[x[i].v]){ ???????????????????vis[x[i].v]=1; ???????????????????que.push(x[i].v); ???????????????} ???????????} ???????}vis[xx]=0; ???}return dis[T]!=inf;}int dfs(int u,int flow){ ???if(u==T) return flow; ???vis[u]=1;int used=0; ???for(int i=head[u];i!=-1;i=x[i].nex){ ???????if(!vis[x[i].v]&&x[i].w&&dis[x[i].v]==dis[u]+x[i].cost){ ???????????int slow=dfs(x[i].v,min(flow-used,x[i].w));used+=slow; ???????????x[i].w-=slow,x[i^1].w+=slow; ???????????cost+=slow*x[i].cost; ???????????if(flow==used) break; ???????} ???}if(!used) dis[u]=-1; ???vis[u]=0; ???return used;}int dinic(){ ???int ans=0; ???while(spfa()){memset(vis,0,sizeof(vis));ans+=dfs(S,INF);} ???return ans;}int n,m,c[MAXN],Sum,d[MAXN],a[MAXN],b[MAXN],sum[MAXN];int main(){ ???memset(head,-1,sizeof(head)); ???n=read(),m=read();S=0,T=n+m+1; ????for(int i=1;i<=n;i++) a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read(); ???for(int i=1;i<=m;i++){ ???????add(S,i,0,1); ???????int u=read(),v=read(); ???????b[u]++,b[v]++; ???????sum[u]++,sum[v]++; ???????add(i,u+m,0,1),add(i,v+m,0,1); ???} ???for(int i=1;i<=n;i++) Sum+=c[i]*a[i]*a[i]+d[i]*b[i]*b[i]; ???for(int i=1;i<=n;i++){ ???????for(int j=1;j<=sum[i];j++){ ???????????add(i+m,T,c[i]*(2*a[i]+1)-d[i]*(2*b[i]-1),1); ???????????a[i]++,b[i]--; ???????} ???}dinic(); ???printf("%d\n",Sum+cost); }