上下界费用流模板

P4553 80人环游世界

朋友中学的模拟

纯模板题

#include 
#define inf 0x7fffffff
#define ll long long
//#define int long long
//#define double long double
#define re register int
#define void inline void
#define eps 1e-18
//#define mod 1e9+7
//#define ls(p) p<<1
//#define rs(p) p<<1|1
//#define ls(p) e[p].l
//#define rs(p) e[p].r
//#define pi acos(-1.0)
#define pb push_back
#define P pair < int , int >
#define mk make_pair
#define fi first
#define se second
using namespace std;
//const int mod=998244353;
const int M=1e8+5;
const int N=4e5+5;//?????????? 4e8.
int n,m,s,t,s_,S,T;
int all[N];
namespace EK
{
	struct node
	{
		int ver,edge,next,cost;
	}e[N];
	int ans;
	int tot=1,head[N];
	int incf[N],pre[N],d[N],v[N];
	void add(int x,int y,int z,int w)
	{
		e[++tot].ver=y;
		e[tot].edge=z;
		e[tot].cost=w;
		e[tot].next=head[x];
		head[x]=tot;
	}
	void addedge(int x,int y,int z,int w)
	{
		add(x,y,z,w);add(y,x,0,-w);
	}
	void ins(int x,int y,int l,int r,int w)
	{
		addedge(x,y,r-l,w);
		all[x]-=l;
		all[y]+=l;
	}
	bool spfa()
	{
		queue < int > q;
		for(re i=0;i<=2*n+10;i++)  d[i]=1e9,v[i]=0;
		incf[s]=1e9;d[s]=0,v[s]=1;q.push(s);
		while(q.size())
		{
			int x=q.front();q.pop();v[x]=0;
			for(re i=head[x];i;i=e[i].next)
			{
				int y=e[i].ver;
				int z=e[i].edge;
				int w=e[i].cost;
				if(!z)  continue;
				if(d[y]>d[x]+w)
				{
					d[y]=d[x]+w;
					incf[y]=min(incf[x],z);
					pre[y]=i;
					if(!v[y])  v[y]=1,q.push(y);
				}
			}
		}
		return d[t]!=1e9;
	}
	void update()
	{
		int x=t;
		while(x!=s)
		{
			int i=pre[x];
			e[i].edge-=incf[t];
			e[i^1].edge+=incf[t];
			x=e[i^1].ver;
		}
		ans+=incf[t]*d[t];
	}
	void ek()
	{
		while(spfa())  update();
	}
}
void solve()
{
	cin>>n>>m;
	s=2*n+1,s_=s+1,t=s_+1;
	S=t+1,T=S+1;
	EK::ins(s,s_,m,m,0);
	for(re i=1;i<=n;i++)
	{
		EK::ins(s_,i,0,m,0);
		EK::ins(i+n,t,0,m,0);
		int x;
		scanf("%d",&x);
		EK::ins(i,i+n,x,x,0);
	}
	for(re i=1;i<=n;i++)  for(re j=i+1;j<=n;j++)
	{
		int x;
		scanf("%d",&x);
		if(x==-1)  continue;
		EK::ins(i+n,j,0,m,x);
	}
	EK::ins(t,s,0,m,0);
	for(re i=1;i<=t;i++)
	{
		if(all[i]>0)  EK::addedge(S,i,all[i],0);
		if(all[i]<0)  EK::addedge(i,T,-all[i],0);
	}
	swap(s,S);swap(t,T);
	EK::ek();
	cout<>T;
    for(int index=1;index<=T;index++)
    {
//        printf("Case #%lld: ",index);
        solve();
//        puts("");
    }
    return 0;
}