蒟蒻求助
查看原帖
蒟蒻求助
307143
一铭君一楼主2020/8/14 20:52

调了一下午了,仍然60pts,求大佬帮忙康康什么问题

#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<utility>
#include<iostream>
#include<list>
#include<ctime>
#include<cmath>
#include<cstdlib>
#include<iomanip>
typedef long long int ll;
inline int read(){
	int fh=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') fh=-1;ch=getchar(); }
	while('0'<=ch&&ch<='9'){ x=(x<<3)+(x<<1)+ch-'0';ch=getchar(); }
	return fh*x;
}
inline int _abs(const int x){ return x>=0?x:-x; }
inline int _max(const int x,const int y){ return x>=y?x:y; }
inline int _min(const int x,const int y){ return x<=y?x:y; }
inline int _gcd(const int x,const int y){ return y?_gcd(y,x%y):x; }
inline int _lcm(const int x,const int y){ return x*y/_gcd(x,y); }
const int maxn=5005;
std::vector<int>v[maxn];
int match[maxn],m,n,col[maxn];//col存每个点的颜色 
bool vis[maxn];
bool dfs(const int x){
	int y;
	for(unsigned int i=0;i<v[x].size();i++)
		if(!vis[y=v[x][i]]){
			vis[y]=1;
			if(!match[y]||dfs(match[y])){ 
				match[y]=x;
				return true;
			}
		}
	return false;
}
inline int APath(){//求增广路 
	int res=0;
	for(int u=0;u<n;u++){
		memset(vis,0,sizeof(vis));
		if(col[u]==0){//如果是黑点就寻找增广路 
			if(dfs(u)) res++;//匹配成功 
		}
	}
	return res;
}
void paint(const int x,const int color){
	int y;
	col[x]=color;
	for(unsigned int i=0;i<v[x].size();i++){
		if(col[y=v[x][i]]==-1){//没有被染色 
			if(color==0) paint(y,1);//1表示白色 
			else paint(y,0);//0表示黑色 
		}
	}
}
int main(){
	n=read(),m=read();
	for(int i=0,x,y;i<m;i++){
		x=read(),y=read();
		if(x==y) continue;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	memset(col,-1,sizeof(col));//一开始都没有被染色 
	for(int i=0;i<n;i++)
		if(col[i]==-1) paint(i,0);//如果没有被染色,默认为黑色 
	int path=APath();
	printf("%d\n",n-path);
	return 0;
}
2020/8/14 20:52
加载中...