调了一下午了,仍然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;
}