本文共 963 字，大约阅读时间需要 3 分钟。

非常水的网络流

看到这么多限制,还有变化的边权…网络流没跑了

每个点拆分为入点和出点,中间连$q$条权值为$a[i]+j\ast b[i]$的边,其中$j\in [0,q-1]$

源点连向$x$的入点

$y$的出点连向汇点,跑最小费用即可

#include 
   
    using namespace std;const int inf = 1e9;const int maxn = 3e6+10;struct edge{
   	int to,nxt,flow,w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int flow,int w){
   	d[++cnt] = (edge){
   v,head[u],flow,w},head[u] = cnt; 	d[++cnt] = (edge){
   u,head[v],0,-w},head[v] = cnt;}int incf[maxn],pre[maxn],s,t,dis[maxn],vis[maxn],n,m,q,a[maxn],b[maxn];bool spfa(){
   	queue
    
     q; q.push( s );	for(int i=0;i<=t;i++)	dis[i] = inf, vis[i] = 0;	incf[s] = inf; vis[s] = 1; dis[s] = 0;	while( !q.empty() )	{
   		int u = q.front(); q.pop();		vis[u] = 0;		for(int i=head[u];i;i=d[i].nxt )		{
   			int v = d[i].to;			if( dis[u]+d[i].w
     
      > n >> m >> q;	s = 0,t = n+n+1;	for(int i=1;i<=n;i++)		cin >> a[i] >> b[i];	for(int i=1;i<=n;i++)	{
   		for(int j=0;j
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/113653588 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！