两连发板子题，水果留恋
#include#include #include using namespace std;const int INF=0x3f3f3f3f;const int maxn=208;struct shit{ int v,next;}edge[maxn*maxn<<1];int tol;int head[maxn];void init(){ tol=0; memset(head,-1,sizeof(head));}void addedge(int u,int v){ edge[tol].v=v; edge[tol].next=head[u]; head[u]=tol++;}int color[maxn];bool judfs(int u,int co){ int i,v; color[u]=co; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(color[v]==co) return false; if(color[v]==-1&&!judfs(v,co^1)) return false; } return true;}bool vis[maxn];int pre[maxn];bool find(int u){ int i,v; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(vis[v]) continue; vis[v]=true; if(pre[v]==-1||find(pre[v])) { pre[v]=u; return true; } } return false;}int hungary(int n){ int i,ans; memset(pre,-1,sizeof(pre)); ans=0; for(i=1;i<=n;i++) { memset(vis,false,sizeof(vis)); if(find(i)) ans++; } return ans;}int main(){ int i,j,n,m,u,v; while(scanf("%d%d",&n,&m)==2) { init(); for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } memset(color,-1,sizeof(color)); bool flag; for(u=1;u<=n;u++) { if(color[u]==-1) { flag=judfs(u,0); if(!flag) break; } } if(u<=n) printf("No\n"); else printf("%d\n",hungary(n)>>1); } return 0;}