题目链接:http://lightoj.com/volume_showproblem.php?problem=1429

思路:这道题还是比较麻烦的,对于求有向图的可相交的最小路径覆盖,首先要解决成环问题,可以先染色缩点重建图,然后就是如何来处理这个路径可以相交这个问题,这里可以用bfs求出任意两点之间是否可达,如果可达,就连边,然后就是HK算法求最大匹配了,最小路径覆盖 = 顶点数 – 最大匹配。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<queue>#include<stack>usingnamespace std;constint MAXN =(+);constint MAXM =(+);int n, m;int cnt, scc_count;boolInstack[MAXN];int low[MAXN], dfn[MAXN], color[MAXN];vector<int> g[MAXN]; stack<int> S;voidTarjan(int u){ low[u]= dfn[u]=++cnt;Instack[u]=true; S.push(u);for(int i =; i <(int)g[u].size(); i++){int v = g[u][i];if(dfn[v]==){Tarjan(v); low[u]= min(low[u], low[v]);}elseif(Instack[v]){ low[u]= min(low[u], dfn[v]);}}if(low[u]== dfn[u]){ scc_count++;int v;do{ v = S.top(); S.pop();Instack[v]=false; color[v]= scc_count;}while(u != v);}}boolIsok[MAXN][MAXN];bool mark[MAXN]; vector<int> reg[MAXN];void bfs(int st){ memset(mark,false,sizeof(mark)); queue<int>que; que.push(st); mark[st]=true;while(!que.empty()){int u = que.front(); que.pop();for(int i =; i <(int)reg[u].size(); i++){int v = reg[u][i];if(!mark[v]){mark[v]=true; que.push(v);}}}}voidBuild(){for(int i =; i <= scc_count; i++){ reg[i].clear();}for(int i =; i <= scc_count; i++){for(int j =; j <= scc_count; j++){if(i != j &&Isok[i][j]){ reg[i].push_back(j);}}}}int lx[MAXN], ly[MAXN];int distx[MAXN], disty[MAXN];boolMaxMatch_bfs(){bool flag =false; memset(distx,,sizeof(distx)); memset(disty,,sizeof(disty)); queue<int> que;for(int i =; i <= scc_count; i++){if(lx[i]==-) que.push(i);}while(!que.empty()){int u = que.front(); que.pop();for(int i =; i <(int)reg[u].size(); i++){int v = reg[u][i];if(disty[v]==){ disty[v]= distx[u]+;if(ly[v]==-) flag =true;else{ distx[ly[v]]= disty[v]+; que.push(ly[v]);}}}}returnflag;}int dfs(int u){for(int i =; i <(int)reg[u].size(); i++){int v = reg[u][i];if(disty[v]== distx[u]+){ disty[v]=;if(ly[v]==|| dfs(ly[v])){ ly[v]= u; lx[u]= v;return;}}}return;}intMaxMatch(){ memset(lx,-,sizeof(lx)); memset(ly,-,sizeof(ly));int res =;while(MaxMatch_bfs()){for(int i =; i <= scc_count; i++){if(lx[i]==-) res +=dfs(i);}}return res;}int main(){int _case, t =; scanf(“%d”,&_case);while(_case–){ scanf(“%d %d”,&n,&m);for(int i =; i <= n; i++){ g[i].clear(); reg[i].clear();}while(m–){int u, v; scanf(“%d %d”,&u,&v); g[u].push_back(v);}//强联通缩点重建图 cnt = scc_count =; memset(dfn,,sizeof(dfn));for(int i =; i <= n; i++){if(dfn[i]==)Tarjan(i);}for(int u =; u <= n; u++){for(int i =; i <(int)g[u].size(); i++){int v = g[u][i];if(color[u]!= color[v]){ reg[color[u]].push_back(color[v]);}}}//bfs求出新图中的任意两点之间是否可达 memset(Isok,false,sizeof(Isok));for(int i =; i <= scc_count; i++){ bfs(i);for(int j =; j <= scc_count; j++){if(mark[j]){Isok[i][j]=true;}}}//对于那些可达的点重新连边Build();//bfs求解最大匹配;//最小路径覆盖 = 顶点数 – 最大匹配数int ans =MaxMatch(); printf(“Case %d: %d\n”, t++, scc_count ans);}return;}

发表回复

您的电子邮箱地址不会被公开。