2021牛客暑期多校训练营 3 C Minimum grid(二分图,费用流,最大流,km(待补))

C Minimum grid

译文:

有一个 n×n 网格,它的一些位置包含非负整数 a_{i,j} ,而其他位置不包含任何内容。

现在,给定一个空的数字网格,以及它的一些位置(这些位置必须包含一个非负整数,而其他位置必须不包含任何内容),以及每行 b_i 中 ai,j 的最大值,ai 的最大值, j 在每一列 c_i 中,您需要找到一种方法来填充网格中的非负整数以满足这些条件。

由于有多种可能的方法,因此要求您找到 ∑ (1≤i,j≤n) a i,j 的最小值,即该网格中数字的总和。
保证有一种方法可以在网格中填充非负整数以满足这些条件。

大意:给出每行的max,每列的max,向网格里填数,同时给出,是数的总和最小

题解:

每行每列,是不是给人一种二分图的感觉?

对于每一个max,先都加进去,在m行的输入中检查是否有行最大,等于列最大的,有则连边。

然后对每一行跑一遍二分图,找到最大,使得减去的max的和最大

二分图解法:

#include <bits/stdc++.h>
#define inf 0x7fffffff
//#define ll long long
#define int long long
//#define double long double
//#define double long long
#define re int
//#define void inline void
#define eps 1e-8
//#define mod 1e9+7
//#define ls(p) p<<1
//#define rs(p) p<<1|1
#define pi acos(-1.0)
#define pb push_back
#define mk make_pair
#define P pair < int , int >
using namespace std;
const int mod=1e9+7;
//const int inf=1e18;
const int M=1e8;
const int N=4e6+5;//??????.???? 4e8
struct node
{
	int ver,next;
}e[N];
int tot,head[N];
int b[N],v[N],c[N];
int ans,n,m,k;
int match[N];
void add(int x,int y)
{
	e[++tot].ver=y;
	e[tot].next=head[x];
	head[x]=tot;
}
bool dfs(int x)
{
	for(re i=head[x];i;i=e[i].next)
	{
		int y=e[i].ver;
		if(v[y])  continue;
		v[y]=1;
		if(!match[y]||dfs(match[y]))
		{
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
void solve()
{
	cin>>n>>m>>k;
	for(re i=1;i<=n;i++)  scanf("%lld",&b[i]),ans+=b[i];
	for(re i=1;i<=n;i++)  scanf("%lld",&c[i]),ans+=c[i];
	for(re i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		if(b[x]==c[y])  add(x,y);
	}
	for(re i=1;i<=n;i++)
	{
		for(re j=0;j<=n;j++)  v[j]=0;
		if(dfs(i))  ans-=b[i];
	}
	cout<<ans<<endl;
} 
signed main() 
{
    int T=1;       
//    cin>>T;
    for(int index=1;index<=T;index++)
    {
        solve();
//        puts("");
    }
    return 0;
}
/*



*/

最大费用最大流:

其实就是一个拆点的思想,还是比较简单的

#include <bits/stdc++.h>
#define inf 0x7fffffff
//#define ll long long
#define int long long
//#define double long double
//#define double long long
#define re int
//#define void inline void
#define eps 1e-8
//#define mod 1e9+7
//#define ls(p) p<<1
//#define rs(p) p<<1|1
#define pi acos(-1.0)
#define pb push_back
#define mk make_pair
#define P pair < int , int >
using namespace std;
const int mod=1e9+7;
//const int inf=1e18;
const int M=1e8;
const int N=4e6+5;//??????.???? 4e8
struct node
{
	int ver,edge,cost,next;
}e[N];
int tot=1,head[N];
int b[N],v[N],c[N];
int ans,n,m,s,t,k;
int d[N],pre[N],incf[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);
}
bool spfa()
{
	queue < int > q;
	for(re i=s;i<=t;i++)  d[i]=-1e18,v[i]=0;
	v[s]=1,d[s]=0,incf[s]=1e18,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;pre[y]=i;incf[y]=min(incf[x],z);
				if(!v[y])  v[y]=1,q.push(y);
			}
		}
	}
	return d[t]>0;
}
int 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;
	}
	return incf[t]*d[t];
}
int ek()
{
	int ans=0;
	while(spfa())  ans+=update();
	return ans;
}
void solve()
{
	cin>>n>>m>>k;
	s=0,t=2*n+1;
	for(re i=1;i<=n;i++)  scanf("%lld",&b[i]),ans+=b[i];
	for(re i=1;i<=n;i++)  scanf("%lld",&c[i]),ans+=c[i];
	for(re i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		if(b[x]==c[y])  addedge(x,y+n,1,b[x]);
	}
	for(re i=1;i<=n;i++)  addedge(s,i,1,0),addedge(i+n,t,1,0);
	cout<<ans-ek()<<endl;
} 
signed main() 
{
    int T=1;       
//    cin>>T;
    for(int index=1;index<=T;index++)
    {
        solve();
//        puts("");
    }
    return 0;
}
/*



*/

最大流:

#include <bits/stdc++.h>
#define inf 0x7fffffff
//#define ll long long
#define int long long
//#define double long double
//#define double long long
#define re int
//#define void inline void
#define eps 1e-8
//#define mod 1e9+7
//#define ls(p) p<<1
//#define rs(p) p<<1|1
#define pi acos(-1.0)
#define pb push_back
#define mk make_pair
#define P pair < int , int >
using namespace std;
const int mod=1e9+7;
//const int inf=1e18;
const int M=1e8;
const int N=4e6+5;//??????.???? 4e8
int n,m,k,s,t;
struct node
{
	int ver,edge,next;
}e[N];
int tot=1,head[N];
int v[8005][8005];
vector < int > a[N][2];
int ma;
int gap[N],d[N];
int b[N],c[N];
void add(int x,int y,int z)
{
	e[++tot].ver=y;
	e[tot].edge=z;
	e[tot].next=head[x];
	head[x]=tot;
}
void addedge(int x,int y,int z)
{
	add(x,y,z);add(y,x,0);
}
void init()
{
	tot=1;
	for(re i=0;i<=n*2+1;i++)  head[i]=0;
}
void bfs()
{
	queue < int > q;
	for(re i=0;i<=n*2+1;i++)  d[i]=gap[i]=0;
	q.push(t),gap[1]=d[t]=1;
	while(q.size())
	{
		int x=q.front();q.pop();
		for(re i=head[x];i;i=e[i].next)
		{
			int y=e[i].ver;
			if(d[y])  continue;
			d[y]=d[x]+1;
			gap[d[y]]++;
			q.push(y);
		}
	} 
}
int dfs(int x,int flow)
{
	if(x==t)  return flow;
	int rest=0;
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].ver;
		int z=e[i].edge;
		if(!z)  continue;
		if(d[x]!=d[y]+1)  continue;
		int k=dfs(y,min(z,flow-rest));
		if(k<=0)  continue;
		e[i].edge-=k;
		e[i^1].edge+=k;
		rest+=k;
		if(rest==flow)  return rest;
	}
	if(--gap[d[x]]==0)  d[s]=4*n*n+1;
	++gap[++d[x]];
	return rest;
}
int isap()
{
	int maxflow=0;
	bfs();
	while(d[s]<=4*n*n)  maxflow+=dfs(s,1e18);
	return maxflow;
}
void solve()
{
	int ans=0;
	cin>>n>>m>>k;
	for(re i=1;i<=n;i++)  scanf("%lld",&b[i]),ans+=b[i],a[b[i]][0].pb(i),ma=max(ma,b[i]);
	for(re i=1;i<=n;i++)  scanf("%lld",&c[i]),ans+=c[i],a[c[i]][1].pb(i),ma=max(ma,c[i]);
	for(re i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		v[x][y]=1;
	}
	for(re i=1;i<=ma;i++)
	{
		int sz=a[i][0].size()+a[i][1].size()+2;
		init();
		int op=0;
		s=sz-1,t=sz;
		int sz1=a[i][0].size(),sz2=a[i][1].size();
		for(re j=0;j<sz1;j++)
		{
			addedge(s,j+1,1);
			for(re k=0;k<sz2;k++)
			{
				int x=a[i][0][j];
				int y=a[i][1][k];
				if(v[x][y])  op=1,addedge(j+1,k+1+sz1,1);
			} 
		}
		if(!op)  continue;
		for(re j=0;j<sz2;j++)  addedge(j+1+sz1,t,1);
		ans-=i*isap();
	}
	cout<<ans<<endl;
} 
signed main() 
{
    int T=1;       
//    cin>>T;
    for(int index=1;index<=T;index++)
    {
        solve();
//        puts("");
    }
    return 0;
}
/*



*/

KM:待补

上一篇:KM算法 O(n^3)最大权完美匹配


下一篇:maven的pom.xml配置json依赖