题目大意：给出一个有向图，问最多能够分成多少个区域，使得每个区域内的任意一对顶点X、Y间，要么X能达到Y，要么Y能到达X。
不错的题目！
具体做法是这样的，因为强连通分量内部的点肯定能互相到达，因此先缩点；然后问题就转化成了有向无环图的最小路径覆盖问题，因为缩点之后的图上的任意一条路径都是满足要求的。
以下是我的代码：
/*
* Author: lee1r
* Created Time: 2011/8/15 11:04:01
* File Name: hdu3861.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define Lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(5007);
const int kMaxm(100007);
struct Edge
{
int u,v;
};
int N,M,cnt,first2[kMaxn],next2[kMaxm],e2[kMaxm];
int n,dfscnt,dfsn[kMaxn],low[kMaxn],id[kMaxn];
stack<int> s;
bool instack[kMaxn];
int nx,ny,maxmatch,first[kMaxn],next[kMaxm];Edge e[kMaxm];
int cx[kMaxn],cy[kMaxn],distx[kMaxn],disty[kMaxn];
int head,tail,q[kMaxn];
void Input()
{
cnt=0;
memset(first2,-1,sizeof(first2));
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++)
{
int u,v;
scanf("%d%d",&u,&v);
cnt++;
e2[cnt]=v;
next2[cnt]=first2[u];
first2[u]=cnt;
}
}
void dfs(int u)
{
dfsn[u]=low[u]=++dfscnt;
s.push(u);
instack[u]=true;
for(int i=first2[u];i!=-1;i=next2[i])
{
int v(e2[i]);
if(!dfsn[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]=min(low[u],dfsn[v]);
}
if(dfsn[u]==low[u])
{
n++;
int v;
do
{
v=s.top();s.pop();
instack[v]=false;
id[v]=n;
}while(v!=u);
}
}
void Tarjan()
{
n=dfscnt=0;
memset(dfsn,0,sizeof(dfsn));
memset(instack,false,sizeof(instack));
for(int i=1;i<=N;i++)
if(!dfsn[i])
dfs(i);
}
void Rebuild()
{
cnt=0;
nx=ny=n;
memset(first,-1,sizeof(first));
for(int u=1;u<=N;u++)
for(int i=first2[u];i!=-1;i=next2[i])
{
int v(id[e2[i]]);
if(id[u]==v)
continue;
bool found(false);
for(int j=first[id[u]];j!=-1;j=next[j])
if(e[j].v==v)
{
found=true;
break;
}
if(found)
continue;
cnt++;
e[cnt].u=id[u];e[cnt].v=v;
next[cnt]=first[id[u]];
first[id[u]]=cnt;
}
}
bool BFS()
{
bool re(false);
head=tail=0;
memset(distx,0,sizeof(distx));
memset(disty,0,sizeof(disty));
for(int i=1;i<=nx;i++)
if(cx[i]==-1)
q[tail++]=i;
while(head!=tail)
{
int h,t;
for(h=head,t=tail;h!=t;h=(h+1)%kMaxn)
{
int u(q[h]);
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v);
if(!disty[v])
{
disty[v]=distx[u]+1;
if(cy[v]==-1)
re=true;
else
{
distx[cy[v]]=disty[v]+1;
q[tail]=cy[v];
tail=(tail+1)%kMaxn;
}
}
}
}
head=t;
}
return re;
}
bool DFS(int u)
{
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v);
if(disty[v]==distx[u]+1)
{
disty[v]=0;
if(cy[v]==-1 || DFS(cy[v]))
{
cx[u]=v;
cy[v]=u;
return true;
}
}
}
return false;
}
void HopcroftKarp()
{
maxmatch=0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
while(BFS())
{
for(int i=1;i<=nx;i++)
if(cx[i]==-1 && DFS(i))
maxmatch++;
}
}
void Output()
{
printf("%d\n",n-maxmatch);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
Input();
Tarjan();
Rebuild();
HopcroftKarp();
Output();
}
return 0;
}
posted on 2011-08-17 00:07
lee1r 阅读(386)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论