HDOJ 3861 - The King’s Problem tarjan求强联通分量&缩点&有向图最小路径覆盖(匈牙利)

发布时间:2016-12-11 6:44:48 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDOJ 3861 - The King’s Problem tarjan求强联通分量&缩点&有向图最小路径覆盖(匈牙利)",主要涉及到HDOJ 3861 - The King’s Problem tarjan求强联通分量&缩点&有向图最小路径覆盖(匈牙利)方面的内容,对于HDOJ 3861 - The King’s Problem tarjan求强联通分量&缩点&有向图最小路径覆盖(匈牙利)感兴趣的同学可以参考一下。

                 题意:                          给了一个图无向联通图..国王还要划分州..若在划分州前两点v,u有路径(v,u)、(u,v)那么他们必须要在同一个州中...并且建立了州以后...一个区域内的任意两点至少要有单向路径..问最少建立多少个州可以满足要求...                  题解:                          首先用tarjan求强联通分量并且缩点...然后题目就转化为了求最小路径覆盖问题...最小路径覆盖问题是指从有向图中选最少的路径覆盖所有的点且任何的点只于一条选取的路径有关联....有向图最小路径覆盖=缩点后的顶点数-二分图最大匹配....         Program: #include<iostream> #include<stdio.h> #include<algorithm> #include<cmath> #include<stack> #include<string.h> #include<queue> #define ll long long #define esp 1e-5 #define MAXN 5006 #define MAXM 100005 #define oo 100000007 using namespace std; struct node { int x,y,next; }line[MAXM]; int Lnum,_next[MAXN],dfn[MAXN],low[MAXN],tp[MAXN],tpnum,DfsIndex,match[MAXN]; bool instack[MAXN],used[MAXN]; stack<int> mystack; void addline(int x,int y) { line[++Lnum].next=_next[x],_next[x]=Lnum; line[Lnum].x=x,line[Lnum].y=y; } void tarjan(int x) { mystack.push(x),instack[x]=true; dfn[x]=low[x]=++DfsIndex; for (int k=_next[x];k;k=line[k].next) { int y=line[k].y; if (!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); }else if (instack[y]) low[x]=min(low[x],dfn[y]); } if (low[x]==dfn[x]) { tpnum++; do { x=mystack.top(); mystack.pop(); instack[x]=false; tp[x]=tpnum; }while (low[x]!=dfn[x]); } } bool dfs(int x) { for (int k=_next[x];k;k=line[k].next) { int y=line[k].y; if (used[y]) continue; used[y]=true; if (!match[y] || dfs(match[y])) { match[y]=x; return true; } } return false; } int getmax(int n) { int sum=0; memset(match,0,sizeof(match)); for (int i=1;i<=n;i++) { memset(used,false,sizeof(used)); sum+=dfs(i); } return sum; } int main() { int i,n,m,cases; scanf("%d",&cases); while (cases--) { scanf("%d%d",&n,&m); Lnum=0,memset(_next,0,sizeof(_next)); while (m--) { int x,y; scanf("%d%d",&x,&y); addline(x,y); } memset(dfn,0,sizeof(dfn)); while (!mystack.empty()) mystack.pop(); memset(instack,false,sizeof(instack)); DfsIndex=tpnum=0; for (i=1;i<=n;i++) if (!dfn[i]) tarjan(i); int temp=Lnum; Lnum=0,memset(_next,0,sizeof(_next)); for (i=1;i<=temp;i++) { int x=tp[line[i].x],y=tp[line[i].y]; if (x==y) continue; addline(x,y); } n=tpnum; printf("%d\n",n-getmax(n)); } return 0; }

上一篇:JDBC 访问数据库的基本步骤(
下一篇:dfs数独--poj2676

相关文章

相关评论