终于来发题解啦!

pdf版题解

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<climits>
using namespace std;
inline int read(){
int f=,ans=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}
return f*ans;
}
queue<int> que;
const int MAXN=;
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=,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,,sizeof(vis));memset(dis,/,sizeof(dis));int inf=dis[];dis[S]=;
que.push(S);
while(!que.empty()){
int xx=que.front();que.pop();
for(int i=head[xx];i!=-;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]=;
que.push(x[i].v);
}
}
}vis[xx]=;
}return dis[T]!=inf;
}
int dfs(int u,int flow){
if(u==T) return flow;
vis[u]=;int used=;
for(int i=head[u];i!=-;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^].w+=slow;
cost+=slow*x[i].cost;
if(flow==used) break;
}
}if(!used) dis[u]=-;
vis[u]=;
return used;
}
int dinic(){
int ans=;
while(spfa()){memset(vis,,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,-,sizeof(head));
n=read(),m=read();S=,T=n+m+;
for(int i=;i<=n;i++) a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
for(int i=;i<=m;i++){
add(S,i,,);
int u=read(),v=read();
b[u]++,b[v]++;
sum[u]++,sum[v]++;
add(i,u+m,,),add(i,v+m,,);
}
for(int i=;i<=n;i++) Sum+=c[i]*a[i]*a[i]+d[i]*b[i]*b[i];
for(int i=;i<=n;i++){
for(int j=;j<=sum[i];j++){
add(i+m,T,c[i]*(*a[i]+)-d[i]*(*b[i]-),);
a[i]++,b[i]--;
}
}dinic();
printf("%d\n",Sum+cost);
}
05-11 13:17