Posted on 2010-07-24 10:56
Uriel 閱讀(1193)
評論(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。。