最小路径覆盖-二分图最大匹配 poj 1422
【最小路径覆盖-二分图最大匹配 poj 1422】
/********************************************************************
** @filepoj1422.cpp
** @authorliuke
** @dateSun May1 16:25:17 2011
** @brief最小路径覆盖-二分图最大匹配
[定义] 设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，
并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，
则称M是一个匹配。
最小路径覆盖[定义]
一个ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，
且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，
那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，
那么每每条路径就是一个弱连通子集．
********************************************************************/
#include
#include
#include
#include
using namespace std;
#define MAX 150
vectorg[MAX];
int path[MAX];
bool vis[MAX];
int num_v,num_r;
bool dfs(int u){
for(int i=0;
i>test;
for(int i=0;
i>num_v>>num_r;
for(int i=1;
i<=num_v;
++i)
g[i].clear();
int v1,v2;
for(int j=0;
j>v1>>v2;
g[v1].push_back(v2);
}
cout< 推荐阅读
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- 普通人通往大神的3个创作路径
- C#|C# 文件路径操作
- 渐冻物语:“眼泪是人间最小的海”
- 剑指offer——最小的K个数
- 实践心得（产品高效实践MVP模型的路径）
- 思科路由映射表控制BGP路径的方法和实例
- 商业变现永不眠|商业变现永不眠(一) — 什么是决定商业化路径的底层逻辑（）
- 地图|高德地图清除指定覆盖物 自定义覆盖物样式（完整dome）
- 浅谈Go切片的值修改是否会覆盖数组的值