时间戳

首页 > 技术文章 > 蓝书二分图例题

蓝书二分图例题

lzqlalala 2019-07-22 11:45 原文

CH6801 棋盘覆盖

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10,M=210;

int head[N],nxt[N*2],to[N*2],a[M][M],vis[N],match[N];
int num,m,n,ans;

void add(int x,int y)
{
	nxt[++num]=head[x],to[num]=y,head[x]=num;
}

bool dfs(int x)
{
	for(int i=head[x],y; i ;i=nxt[i])
		if(!vis[y=to[i]])
		{
			vis[y]=1;//一开始写在外面，错了; 
			if(!match[y] || dfs(match[y]))
			{
				match[x]=y; match[y]=x;// 一开始没写第二句，错了； 
				return true ;
			}
		}
	return false ;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y; scanf("%d%d",&x,&y);
		a[x][y]=1;
	}
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]==1) continue ;
			int x=i*n+j-n;
			
			if(j<n && !a[i][j+1]) add(x,x+1);
			if(j>1 && !a[i][j-1]) add(x,x-1);
			
			if(i<n && !a[i+1][j]) add(x,x+n);
			if(i>1 && !a[i-1][j]) add(x,x-n);
		}
	
	for(int i=1;i<=n*n;i++)
		if(!match[i])
		{
			memset(vis,0,sizeof(vis));
			if(dfs(i)) ans++;
		}
		
	cout<<ans<<endl; 
	return 0;	
}

CH6802 车的放置

#include<bits/stdc++.h>
using namespace std;
const int N=210,M=1e3+10;

int head[M],to[M],nxt[M],a[N][N],match[M],vis[M];
int n,m,t,num,ans;

int read()
{
	int x; scanf("%d",&x);
	return x;
}

void add(int x,int y)
{
	nxt[++num]=head[x],to[num]=y,head[x]=num;
}

bool dfs(int x)
{
	for(int i=head[x],y; i ;i=nxt[i])
		if(!vis[y=to[i]])
		{
			vis[y]=1;
			if(!match[y] || dfs(match[y]))
			{
				match[y]=x,match[x]=y;
				return true ;
			}
		}
	return false ;
}

int main()
{
	n=read(),m=read(),t=read();
	for(int i=1;i<=t;i++)
	{
		int x=read(),y=read();
		a[x][y]=1;
	}
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!a[i][j])
				add(i,n+j),add(n+j,i);
				
	for(int i=1;i<=n;i++)
		if(!match[i])
		{
			memset(vis,0,sizeof(vis));
			if(dfs(i)) ans++;
		}
	
	cout<<ans<<endl;
	return 0;
}

CH6803导弹防御塔

坑人题。T1单位给的是秒，T2单位给的是分钟。坑了我两个小时。
emmm试了一下用vector代替链式前向星，挺爽的。

#include<bits/stdc++.h>
using namespace std;
const int N=100,M=5e3;
const double EPS=1e-8;

vector<int> G[N];
int tx[N],ty[N],mx[N],my[N],id[M];
int match[M],vis[M];
int n,m,num,tot;
double T1,T2,V,tme[M];

int read()
{
    int x; scanf("%d",&x);
    return x;
}

double dis(int i,int j)
{
    double x=tx[i]-mx[j],y=ty[i]-my[j];
    return sqrt(x*x+y*y);
}

void init(double mid)
{
    memset(match,0,sizeof(match));
	for(int i=1;i<=m;i++) G[i].clear();
	for(int i=1;i<=m;i++)
		for(int j=1;j<=tot;j++)
			if(dis(id[j],i)/V+tme[j]<=mid) G[i].push_back(j);
}

bool dfs(int x)
{
    for(auto y:G[x])
        if(!vis[y])
        {//puts("?");
            vis[y]=1;
            if(!match[y] || dfs(match[y]))
            {
                match[y]=x;
                return true ;
            }
        }
    return false ;
}

bool check(double mid)
{
    init(mid);
    for(int i=1;i<=m;i++)
    {
        memset(vis,0,sizeof(vis));
   	    if(!dfs(i)) return false ;
    }
    return true ;
}

int main()
{
	//freopen("my.out","w",stdout);
    n=read(),m=read(),T1=read(),T2=read(),V=read(); 
    for(int i=1;i<=m;i++) mx[i]=read(),my[i]=read();
    for(int i=1;i<=n;i++) tx[i]=read(),ty[i]=read();
	T1/=60,tot=n*m;

	for(int i=1;i<=n;i++)
		for(int j=1;j<=tot;j++)
		{
			int k=(i-1)*m+j;
			id[k]=i,tme[k]=(j-1)*(T1+T2)+T1;
		}

    double l=T1,r=1e5;
    while(l+EPS<r)
    {
        double mid=(l+r)/2;
        if(check(mid))
            r=mid;
        else l=mid;
        
        //break ;
    }
    printf("%.6lf\n",r);

    return 0;
}

POJ1325 Machine Schedule

因为机器一开始模式是0，所以a[i]或b[i]为0的不会使机器重启，所以不要加边。

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1010;

int head[N],to[M],nxt[M];
int match[M],vis[M];
int n,m,k,num,ans;

void add(int x,int y)
{
	nxt[++num]=head[x],to[num]=y,head[x]=num;
}

bool dfs(int x)
{
	for(int i=head[x],y; i!=-1; i=nxt[i])
		if(!vis[y=to[i]])
		{//puts("?");
			vis[y]=1;
			if(match[y]==-1 || dfs(match[y]))
			{
				match[y]=x;
				return true ;
			}
		}
	return false ;
}

int main()
{
	while(scanf("%d",&n)!=EOF && n)
	{
		scanf("%d%d",&m,&k);
		ans=num=0;
		memset(match,-1,sizeof match);
		memset(head,-1,sizeof head);
		for(int i=1;i<=k;i++)
		{
			int a,x,y; scanf("%d%d%d",&a,&x,&y);
			if(x && y) add(x,y+n);
		}
	
		for(int i=0;i<n;i++)
		{
			memset(vis,0,sizeof vis);
			if(dfs(i)) ans++;
		}
		cout<<ans<<endl;
	}
}

POJ2226

二分图的最小点覆盖

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define fi first
#define se second
#define Pit pair<int,int>
using namespace std;
typedef long long LL;
const int N=55;

int read()
{
	int x=0,p=1; char ch=getchar();
	while((ch<'0' || ch>'9') && ch!='-') ch=getchar();
	if(ch=='-') p=-1,ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*p;
}
/*-----------------------------------------------------------------*/

vector<int> G[N*N];
char s[N][N];
int a1[N][N],a2[N][N],vis[N*N],match[N*N];
int n,m,cntn,cntm,ans;

bool dfs(int x)
{
	for(auto y:G[x])
		if(!vis[y])
		{
			vis[y]=1;
			if(!match[y] || dfs(match[y]))
			{
				match[y]=x; return true ;
			}
		}
	return false ;
}

int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);

	n=read(),m=read();
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			if(s[i][j]=='*')
			{
				if(s[i][j-1]!='*') cntn++;
				a1[i][j]=cntn;
			}
	}
	for(int j=1;j<=m;j++)
	{
		for(int i=1;i<=n;i++)
			if(s[i][j]=='*')
			{
				if(s[i-1][j]!='*') cntm++;
				a2[i][j]=cntm+cntn;
			}
	}

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a1[i][j] && a2[i][j]) G[a1[i][j]].push_back(a2[i][j]);

	for(int i=1;i<=cntn;i++)
	{
		memset(vis,0,sizeof vis);
		ans+=dfs(i);
	}
	printf("%d\n",ans);
	return 0;
}

推荐阅读