求助 50pts
查看原帖
求助 50pts
678087
fangzichang楼主2022/8/5 21:15

输出日常差1,,

#include<bits/stdc++.h>
#define int long long
//马克思主义万岁英特纳雄耐尔一定要实现
using namespace std;
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
#define cin(x) read(x)
const int N=1e4+10;
int n,m,a[N][N],k[N],col[N];
//洛谷判mle用的是实际使用内存
bool vis[N];
void color(int u,int c){
	col[u]=c;
	for(int i=1;i<=n;i++){
		if(a[u][i]&&!col[i]){
			color(i,3-c);
		}
			
	}
}
bool dfs(int u){
	for(int i=1;i<=n;i++)
		if(a[u][i]&&!vis[i]){
			vis[i]=1;
			if(!k[i]||dfs(k[i])){
				k[i]=u;
				return 1;
			}
		}
	return 0;
}
int match(){
	int res=0;
	for(int i=1;i<=n;i++){
		if(col[i]!=1)continue;
		for(int j=1;j<=n;j++)vis[j]=0;
		res+=dfs(i);
	}
	return res;
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		cin(x);
		cin(y);
		a[x][y]=a[y][x]=1;
	}
	for(int i=1;i<=n;i++)if(!col[i])color(i,1);
	cout<<n-match()<<endl;
	return 0;
}

rt,不把输出减一#2#3#5#6#7WA,减一了其余WA,总之50pts求调,,,悬赏两个关注

2022/8/5 21:15
加载中...