网站开发具体的工作内容,wordpress单机版,项目网站,苏州网站建设制作方案题意#xff1a;每一条边至少有一个端点要涂颜色#xff0c;问最少涂几个点 思路#xff1a;最小顶点覆盖#xff1a;用最少的点#xff0c;让每条边都至少和其中一个点关联#xff0c;显然是道裸最小顶点覆盖题#xff1b; 参考#xff1a;二分图 代码#xff1a; #i… 题意每一条边至少有一个端点要涂颜色问最少涂几个点 思路最小顶点覆盖用最少的点让每条边都至少和其中一个点关联显然是道裸最小顶点覆盖题 参考二分图 代码 #includeiostream
#includealgorithm
#includecstdio
#includestdio.h
#includestring.h
#includequeue
#includecmath
#includemap
#includeset
#includevector
using namespace std;
typedef unsigned long long ull;
const int maxn 500 10;
const ull seed 131;
struct Edge{int v, next;
}edge[maxn * maxn * 2];
int head[maxn], match[maxn], vis[maxn], tot;
void addEdge(int u, int v){edge[tot].v v;edge[tot].next head[u];head[u] tot;
}
bool dfs(int u){for(int i head[u]; i ! -1; i edge[i].next){int v edge[i].v;if(!vis[v]){vis[v] 1;if(match[v] -1 || dfs(match[v])){match[v] u;match[u] v;return true;}}}return false;
}
int solve(int n){int ans 0;memset(match, -1, sizeof(match));for(int i 1; i n; i){if(match[i] -1){memset(vis, 0, sizeof(vis));if(dfs(i)) ans;}}return ans;
}
int main(){int n, m;while(~scanf(%d%d, n, m)){memset(head, -1, sizeof(head));tot 0;for(int i 1; i m; i){int u, v;scanf(%d%d, u, v);addEdge(u, v);addEdge(v, u);}printf(%d\n, solve(n));}return 0;
} 转载于:https://www.cnblogs.com/KirinSB/p/9898786.html
