很裸的费用流。会费用流应该都会做。
因为我们是选择每个x去匹配y。
然后我们可以直接源点S到x,y到汇点T。
然后点权会变,我们直接拆点,并且把两点之间拆成q条边即可。
AC代码:
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> #define int long long using namespace std; const int inf=0x3f3f3f3f3f3f3f3f; const int N=210,M=1e6+10; int n,m,q,s,t,d[N],st[N],vis[N]; int head[N],nex[M],to[M],w[M],flow[M],tot=1; inline void ade(int a,int b,int c,int d){ to[++tot]=b; nex[tot]=head[a]; w[tot]=d; flow[tot]=c; head[a]=tot; } inline void add(int a,int b,int c,int d){ade(a,b,c,d); ade(b,a,0,-d);} inline int spfa(){ queue<int> q; q.push(s); memset(st,0,sizeof st); memset(d,0x3f,sizeof d); d[s]=0; while(q.size()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=nex[i]) if(flow[i]&&d[to[i]]>d[u]+w[i]){ d[to[i]]=d[u]+w[i]; if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1; } } return d[t]<inf; } int dfs(int x,int f){ if(x==t) return f; st[x]=1; int fl=0; for(int i=head[x];i&&f;i=nex[i]){ if(flow[i]&&d[to[i]]==d[x]+w[i]&&!st[to[i]]){ int mi=dfs(to[i],min(f,flow[i])); flow[i]-=mi,flow[i^1]+=mi,fl+=mi,f-=mi; } } return fl; } inline int zkw(){ int res=0; while(spfa()) res+=dfs(s,inf)*d[t]; return res; } signed main(){ cin>>n>>m>>q; t=205; for(int i=1,a,b;i<=n;i++){ cin>>a>>b; for(int j=1;j<=q;j++) add(i,i+n,1,a+(j-1)*b); } for(int i=1,a,b;i<=m;i++) cin>>a>>b,add(a+n,b,inf,0),add(b+n,a,inf,0); for(int i=1,x;i<=q;i++) cin>>x,add(s,x,1,0); for(int i=1,y;i<=q;i++) cin>>y,add(y+n,t,1,0); cout<<zkw(); return 0; }