Posted on 2010-07-24 10:56
Uriel 阅读(1185)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
图论
最近在做图论，并且打算暑假军训之前(再次抱怨学校大二升大三暑假集训的制度...)除了每周5场组队赛之外大部分时间用来看图论，虽然也不知道来不来得及。。。
强连通的问题看了好几天，因为组队赛占用很多时间，所以相关题也没做多少，依然觉得建图很困难。。
这题题意绕人。。转述某大牛Blog的解释：2*N 个顶点的2 分图，并且给了一个完美匹配(Perfect Matching)以及每个顶点可以连接的其他的顶点。题目要求是否可以确定某 2 个顶点连边后，其他 2*(N - 1) 个顶点的 2 分图是否可以构成完美匹配
膜拜DY大牛Blog里的解释，还是不怎么明白，自己画图之后感觉是如果是在一个强连通分量中的话这个儿子选另外的女生的话原本跟他配对的女生可以找到另外的男生，所以题目转化为对每个儿子求跟他在同一个连通分量中的女生有哪些，按编号升序输出
这题之前做过3题强连通分量的题，都是用Kosaraju写的，这题尝试了一下Tarjan+并查集(基本是照着解题报告敲的。。)。。
对比一下时间：
Kosaraju：G++(不加读入输出优化)：11516Ms
G++(加读入输出优化)：2172Ms
Tarjan+Disjoint Sets：C++(不加读入输出优化)：3750Ms
C++(加读入输出优化)：4579Ms
G++(不加读入输出优化)：10125Ms
G++(加读入优化)：8579Ms
G++(加读入输出优化)：500Ms
下面贴下很挫的代码：
Version：Kosaraju
//Problem: 1904 User: Uriel
//Memory: 3660K Time: 2172MS
//Language: G++ Result: Accepted
//Version [vector & Kosaraju]
//2010.07.24
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAXN 5010*2
int v,m;
int flag;
int link[MAXN];
int out[MAXN];
int size[MAXN];
int order[MAXN];
int num;
int res[MAXN],nres;
bool vis[MAXN];
vector<int>adja[MAXN];
vector<int>adjb[MAXN];
int in()
{
char ch;
int a=0;
while((ch=getchar())==' ' || ch=='\n');
a*=10;
a+=ch-'0';
while((ch=getchar())!=' ' && ch!='\n'){
a*=10;a+=ch-'0';
}
return a;
}
void Out(int a){
if(a>=10)Out(a/10);
putchar(a%10+'0');
}
void DFS1(int x){
vis[x]=true;
for(int i=0;i<adja[x].size();i++)
if(!vis[adja[x][i]])DFS1(adja[x][i]);
order[++num]=x;
}
void DFS2(int x){
vis[x]=true;
link[x]=flag;
size[flag]++;
for(int i=0;i<adjb[x].size();i++)
if(!vis[adjb[x][i]])DFS2(adjb[x][i]);
}
void Kosaraju(){
int i;
memset(vis,0,sizeof(vis));
num=0;
for(i=1;i<=v;i++)
if(!vis[i])DFS1(i);
memset(vis,0,sizeof(vis));
memset(size,0,sizeof(size));
flag=0;
for(i=num;i>=1;i--){
if(!vis[order[i]]){
flag++;
DFS2(order[i]);
}
}
}
int main()
{
int x,i,j;
v=in();
for(i=1;i<=v;i++){
m=in();
for(j=0;j<m;j++){
x=in();
adja[i].push_back(x+v);
adjb[x+v].push_back(i);
}
}
for(j=1;j<=v;j++){
x=in();
adja[x+v].push_back(j);
adjb[j].push_back(x+v);
}
Kosaraju();
for(i=1;i<=v;i++){
nres=0;
for(j=0;j<adja[i].size();j++){
if(link[i]==link[adja[i][j]])res[nres++]=adja[i][j]-v;
}
sort(res,res+nres);
Out(nres);
for(j=0;j<nres;j++){
putchar(' ');
Out(res[j]);
}
putchar('\n');
}
return 0;
}
Version：Tarjan+disjoint sets
//Problem: 1904 User: Uriel
//Memory: 3044K Time: 610MS
//Language: G++ Result: Accepted
//Version [Tarjan+disjoint sets]
//2010.07.24
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node{
int x,y,next;
};
int e,n,res;
int head[5000],co[5000],father[5000],link[5000],order[5000];
node p[1000000];
int in(){
char ch;
int a=0;
while((ch=getchar())==' ' || ch=='\n');
a*=10;
a+=ch-'0';
while((ch=getchar())!=' ' && ch!='\n'){
a*=10;a+=ch-'0';
}
return a;
}
void out(int a){
if(a>=10)out(a/10);
putchar(a%10+'0');
}
void addedge(int x,int y){
p[e].x=x;p[e].y=y;p[e].next=head[x];
head[x]=e++;
}
void init(){
int num,x;
e=0;
memset(head,-1,sizeof(head));
memset(link,0,sizeof(link));
memset(order,0,sizeof(order));
n=in();
for(int i=1;i<=n;i++){
num=in();
for(int j=1;j<=num;j++){
x=in();
addedge(i,x+n);
}
}
for(int i=1;i<=n;i++){
x=in();
addedge(x+n,i);
}
}
int Find(int x){
if(father[x]==x)return x;
father[x]=Find(father[x]);
return father[x];
}
void DFS(int x){
for(int i=head[x];i!=-1;i=p[i].next){
if(order[p[i].y]==0){
order[p[i].y]=order[x]+1;
DFS(p[i].y);
if(order[Find(p[i].y)]<order[Find(x)])father[x]=father[p[i].y];
}
else if(co[Find(p[i].y)]==0 && order[Find(p[i].y)]<order[Find(x)])father[x]=father[p[i].y];
}
co[x]=1;
}
void Tarjan(){
for(int i=1;i<=n+n;i++)father[i]=i;
for(int i=1;i<=n+n;i++){
if(order[i]==0){
order[i]=1;
DFS(i);
}
}
for(int i=1;i<=n+n;i++)Find(i);
}
int main()
{
init();
Tarjan();
for(int i=1;i<=n;i++){
res=0;
for(int j=head[i];j!=-1;j=p[j].next){
if(father[i]==father[p[j].y])link[res++]=p[j].y-n;
}
out(res);
sort(link,link+res);
for(int j=0;j<res;j++){
putchar(' ');
out(link[j]);
}
puts("");
}
return 0;
}
继续好好学图论。。继续膜拜DY大牛Blog。。