大致题意:
给出一个由n个顶点m条边组成的无回路有向图。求最少可以同时存在多少路径,使得这些路径可以覆盖所有的点(注:每个都点可以被多条路径覆盖)。
大致思路:
最小路径覆盖的一点小小变形,由于这里的点可以被重复覆盖,所以除了按照普通求最小路径覆盖的方式建立二分图以外,还要对原图用floyd求一遍传递闭包,并更新二分图。接下来用点数n减去最大匹配得到的就是答案。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000;
int c,d;
int map[nMax][nMax];
bool vis[nMax];
int linkk[nMax];
int dfs(int s){
for(int i=1;i<=d;i++){
if(!vis[i]&&map[s][i]){
vis[i]=1;
if(linkk[i]==-1||dfs(linkk[i])){
linkk[i]=s;
return 1;
}
}
}
return 0;
}
void floyd(int n){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(map[i][k]&&map[k][j]){
map[i][j]=1;
}
}
}
}
}
int main(){
int n,m,a,b,ans,i,j;
while(scanf("%d%d",&n,&m)&&(n||m)){
c=d=n;
ans=0;
memset(map,0,sizeof(map));
while(m--){
scanf("%d%d",&a,&b);
map[a][b]=1;
}
floyd(n);
memset(linkk,-1,sizeof(linkk));
for(i=1;i<=c;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d\n",n-ans);
}
return 0;
}
分享到:
相关推荐
poj 3593 Sea Base Exploration.md
NULL 博文链接:https://128kj.iteye.com/blog/1754756
这是西北工业大学的POJ试题的答案,欢迎下载!
* 最短路径算法:例如 Dijkstra、Bellman-Ford、Floyd、Heap+Dijkstra,例如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最小生成树算法:例如 Prim、Kruskal,例如 poj1789、poj2485、poj1258、...
网上整理的一些poj刷题指南。 poj地址:http://poj.org
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
twilight-poj-solutionPOJ () solution by twilight想当年要找一题的分析, 解答实在太难了现在都是开源的时代了, 干脆把Archive放到GitHub上, 供后来人参考.POJ ID: 部分题解: 转载请注明出处~
poj 算法题在poj.org上做的一些算法题poj.org 账号:xxfeixiang题目地址:例如,第1001题的地址为:
POJ 3267 POJ 1260 POJ 1015 POJ 3176 POJ 1080 POJ 1159 POJ 2533 POJ 1836 Leetcode 70 Leetcode 309 搜索 DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索...
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练)
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj2516代码最小费用最大流
poj分类poj分类poj分类poj分类
NULL 博文链接:https://200830740306.iteye.com/blog/603493
NULL 博文链接:https://128kj.iteye.com/blog/1705139
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告