1
#include<iostream>
2
using namespace std;
3
#define MAX 5000
4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
5
char str[MAX+2];
6
char re_str[MAX+2];
7
//int res[MAX+1][MAX+1]; //MLE
8
int res[2][MAX+1];
9
int n;
10![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
11
void dp()
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
13
int i,j;
14
for(j=0;j<=n;j++)
15
res[0][j]=j;
16
res[1][0]=1;
17
for(i=1;i<=n;i++)
18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
19
res[i%2][0]=i;
20
for(j=1;j<=n;j++)
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
22
if(str[i]==re_str[j])
23
res[i%2][j]=res[(i-1)%2][j-1];
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
25
res[i%2][j]=min(res[(i-1)%2][j],res[i%2][j-1])+1;
26
}
27
}
28
}
29
}
30
int main()
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
32
int i;
33
scanf("%d",&n);
34
for(i=1;i<=n;i++)
35![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
36
scanf(" %c",&str[i]);
37
re_str[n-i+1]=str[i];
38
}
39
dp();
40
printf("%d\n",res[n%2][n]>>1);
41
return 0;
42
}
//
posted @
2009-05-10 14:38 wyiu 阅读(150) |
评论 (0) |
编辑 收藏
![](http://www.cppblog.com/Emoticons/QQ/14.gif)
第一题完全靠自己的DP,一遍AC
![](http://www.cppblog.com/Emoticons/QQ/laf.gif)
高兴...
1
#include<iostream>
2
using namespace std;
3
#define MAX 100
4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
5
int table['T'+1]['T'+1]; //scoring matrix
6
int score[MAX+1][MAX+1]; //score[i][j]表示a串有i个基,b串j个基的最大score
7
char a[MAX+1]; //string a
8
char b[MAX+1]; //string b
9
int la; //length of a
10
int lb; //length of b
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
void init()
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
14
table['A']['A']=5;
15
table['A']['C']=-1;
16
table['A']['G']=-2;
17
table['A']['T']=-1;
18
table['A']['-']=-3;
19![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
20
table['C']['A']=-1;
21
table['C']['C']=5;
22
table['C']['G']=-3;
23
table['C']['T']=-2;
24
table['C']['-']=-4;
25![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
26
table['G']['A']=-2;
27
table['G']['C']=-3;
28
table['G']['G']=5;
29
table['G']['T']=-2;
30
table['G']['-']=-2
31
;
32
table['T']['A']=-1;
33
table['T']['C']=-2;
34
table['T']['G']=-2;
35
table['T']['T']=5;
36
table['T']['-']=-1;
37![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
38
table['-']['A']=-3;
39
table['-']['C']=-4;
40
table['-']['G']=-2;
41
table['-']['T']=-1;
42
}
43
void dp()
44![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
45
int i,j;
46
score[0][0]=0;
47
for(i=1;i<=la;i++)
48
score[i][0]=score[i-1][0]+table[a[i]]['-'];
49
for(i=1;i<=lb;i++)
50
score[0][i]=score[0][i-1]+table['-'][b[i]];
51
for(i=1;i<=la;i++)
52
for(j=1;j<=lb;j++)
53
score[i][j]=max(score[i-1][j-1]+table[a[i]][b[j]],max(score[i][j-1]+table['-'][b[j]],score[i-1][j]+table[a[i]]['-']));
54
}
55![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
56![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
57
int main()
58![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
59
int T;
60
scanf("%d",&T);
61
init();
62
while(T--)
63![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
64
memset(a,0,sizeof(a));
65
memset(b,0,sizeof(b));
66
scanf("%d",&la);
67
scanf("%s",a+1);
68
scanf("%d",&lb);
69
scanf("%s",b+1);
70
dp();
71
printf("%d\n",score[la][lb]);
72
}
73
return 0;
74
}
75![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2009-05-02 16:21 wyiu 阅读(170) |
评论 (0) |
编辑 收藏
//将第i行到第j行的每列求和,保存于csum,然后求最大字串和
1
#include<iostream>
2
using namespace std;
3
#define MAXN 100
4
#define _INF -10000000
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
int a[MAXN+1][MAXN+1];
7
int csum[MAXN+1];
8![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
9
int maxSubArray(int csum[],int n)
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
11
int b=0,max=_INF,j;
12
for(j=1;j<=n;j++)
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
14
if(b>0) b+=csum[j];
15
else b=csum[j];
16
if(b>max) max=b;
17
}
18
return max;
19
}
20![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
21
int main()
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
23
int n,i,j,k,t,res=_INF;
24
scanf("%d",&n);
25
for(i=1;i<=n;i++)
26
for(j=1;j<=n;j++)
27
scanf("%d",&a[i][j]);
28
29
for(i=1;i<=n;i++)
30![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
31
memset(csum,0,sizeof(csum));
32
for(j=i;j<=n;j++)
33![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
34
for(k=1;k<=n;k++)
35
csum[k]+=a[j][k];
36
t=maxSubArray(csum,n);
37
if(t>res) res=t;
38
}
39
}
40
printf("%d\n",res);
41
return 0;
42
}
43![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2009-05-02 13:58 wyiu 阅读(99) |
评论 (0) |
编辑 收藏
一遍SPFA求去的最短路径,把图的边逆向,再一遍SPFA,求出回来的最短路径...
SPFA其实是Bellman-Ford使用队列的优化
1
#include<iostream>
2
#include<queue>
3
using namespace std;
4
#define INF 2147483647 //2,147,483,647
5
#define MAXP 1000000 //1,000,000
6
#define MAXSUM 1000000000 //1,000,000,000
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
struct Edge
9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
10
//int src;
11
int vertex;
12
int weight;
13
Edge *next;
14
};
15![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
16
Edge edge[MAXP*2+1];
17
Edge *go[MAXP+1];
18
Edge *back[MAXP+1];
19
int dis[MAXP+1];
20
bool flag[MAXP+1]; //false denote that the vertex is not in the queue
21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
22
void creatlist(int vn,int en)
23![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
24
int s,d,w,i,j;
25
for(i=1;i<=vn;i++)
26![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
27
go[i]=NULL;
28
back[i]=NULL;
29
flag[i]=false;
30
}
31
for(i=1,j=1;i<=en;i++)
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
33
scanf("%d%d%d",&s,&d,&w);
34
edge[j].vertex=d;
35
edge[j].weight=w;
36
edge[j].next=go[s];
37
go[s]=&edge[j++];
38
39
edge[j].vertex=s;
40
edge[j].weight=w;
41
edge[j].next=back[d];
42
back[d]=&edge[j++];
43
}
44
}
45![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
46
void spfa(Edge *adjlist[],int vn,int src)
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
48
int i,u,v,tmp;
49
Edge *p;
50
queue<int> Queue;
51
for(i=1;i<=vn;i++)
52
dis[i]=INF;
53
dis[src]=0;
54
Queue.push(src);
55
while(!Queue.empty())
56![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
57
u=Queue.front();
58
Queue.pop();
59
flag[u]=false;
60
p=adjlist[u];
61
while(p!=NULL)
62![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
63
tmp=dis[u]+p->weight;
64
65
v=p->vertex;
66
if(dis[v] > tmp)
67![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
68
dis[v]=tmp;
69
if(flag[v]==false)
70![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
71
Queue.push(v);
72
flag[v]=true;
73
}
74
}
75![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//*
76
if(dis[p->vertex] > tmp)
77
{
78
dis[p->vertex]=tmp;
79
if(flag[p->vertex]==false)
80
{
81
Queue.push(p->vertex);
82
flag[p->vertex]=true;
83
}
84
}*/
85
p=p->next;
86
}
87
}
88
}
89![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
90
int main()
91![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
92
int n,p,q,i;
93
__int64 sum;
94
scanf("%d",&n);
95
while(n--)
96![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
97
scanf("%d%d",&p,&q);
98
creatlist(p,q);
99
sum=0;
100
spfa(go,p,1);
101
for(i=1;i<=p;i++)
102
sum+=dis[i];
103
spfa(back,p,1);
104
for(i=1;i<=p;i++)
105
sum+=dis[i];
106
printf("%I64d\n",sum);
107
}
108
return 0;
109
}
posted @
2009-04-27 01:31 wyiu 阅读(126) |
评论 (0) |
编辑 收藏
above[i]记录i方块之上的方块数
rank[i]记录树上总节点数(根节点)
M x y时把y所在树加到x所在树后,原x所在树的节点的above大小得更新,由于有路经压缩...具体看程序吧
1
#include<iostream>
2
using namespace std;
3
#define MAXN 30000
4
#define MAXP 100000
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
int parent[MAXN+1];
7
int rank[MAXN+1]; //该数的结点(方块)数
8
int above[MAXN+1]; //记录该方块之上有的方块数
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10
void init(int n=MAXN)
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
12
int i=0;
13
for(i=1;i<=n;i++)
14![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
15
parent[i]=-1;
16
rank[i]=1;
17
}
18
}
19![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
20
int find(int x)
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
22
int p = x,temp,tp;
23
while( parent[p] > 0) p = parent[p];
24
while( x != p )
25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
26
tp=temp = parent[x];
27
parent[x] = p;
28
while(temp!= p) //难理解的地方
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
30
above[x]+=above[temp];
31
temp=parent[temp];
32
}
33
x = tp;
34
}
35
return p;
36
}
37![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
38
void Union(int x,int y)
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
40
int root1=find(x),
41
root2=find(y);
42
if(root1==root2) return ;
43
above[root2]=rank[root1];
44
rank[root1]+=rank[root2];
45
parent[root2]=root1;
46
}
47![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
48
int main()
49![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
50
int P,x,y;
51
char c;
52
init();
53
scanf("%d",&P);
54
while(P--)
55![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
56
scanf(" %c",&c,&x,&y);
57
if(c=='M')
58![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
59
scanf("%d%d",&x,&y);
60
Union(x,y);
61![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
62
scanf("%d",&x);
63
y=find(x);
64
printf("%d\n",rank[y]-above[x]-1);
65
}
66
}
67
return 0;
68
}
69
70![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
71
72![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2009-04-23 20:57 wyiu 阅读(175) |
评论 (0) |
编辑 收藏
1
#include<iostream>
2
using namespace std;
3
#define MAXN 50000
4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
5
int parent[MAXN+1];
6![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
7
void init(int n)
8![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
9
int i;
10
for(i=1;i<=n;i++)
11
parent[i]=-1;
12
}
13![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
14![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
15
int find(int x)
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
17
if(parent[x]<0)
18
return x;
19
else return parent[x]=find(parent[x]);
20
21
}
22![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
23
void Union(int x,int y)
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
25
int root1=find(x),
26
root2=find(y);
27
if(root1==root2) return;
28
if(parent[root1]<parent[root2])
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
30
parent[root1]+=parent[root2];
31
parent[root2]=root1;
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
33
parent[root2]+=parent[root1];
34
parent[root1]=root2;
35
}
36
}
37![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
38![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
39
int main()
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
41
int n,m,x,y,i,k=1,sum;
42
memset(parent,-1,sizeof(parent));
43
while( scanf("%d%d",&n,&m)==2 && n!=0 )
44![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
45
sum=0;
46
while(m--)
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
48
scanf("%d%d",&x,&y);
49
Union(x,y);
50
}
51
for(i=1;i<=n;i++)
52![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
53
if(parent[i]<0)
54
sum++;
55
parent[i]=-1;
56
}
57
printf("Case %d: %d\n",k++,sum);
58
}
59
return 0;
60
}
posted @
2009-04-22 20:20 wyiu 阅读(81) |
评论 (0) |
编辑 收藏
1
#include<iostream>
2
using namespace std;
3
#define MAXN 30000
4
#define MAXM 500
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
int parent[MAXN];
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
void init(int n=MAXN)
9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
10
int i;
11
for(i=0;i<n;i++)
12
parent[i]=-1;
13
}
14
int find(int x)
15![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
16
if(parent[x]<0)
17
return x;
18
else return parent[x]=find(parent[x]);
19
}
20![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
21
int Union(int x,int y)
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
23
int root1=find(x),
24
root2=find(y);
25
if(root1==root2) return root1;
26
if(parent[root1]<parent[root2])
27![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
28
parent[root1]+=parent[root2];
29
parent[root2]=root1;
30
return root1;
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
32
parent[root2]+=parent[root1];
33
parent[root1]=root2;
34
return root2;
35
}
36
}
37
int main()
38![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
39
int n,m,i,j,k,x,root;
40
while( scanf("%d%d",&n,&m)==2 && n!=0 )
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
42
init(n);
43
for(i=0;i<m;i++)
44![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
45
scanf("%d",&k);
46
for(j=1;j<=k;j++)
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
48
scanf("%d",&x);
49
if(j==1) root=x;
50
root=Union(root,x);
51
}
52
}
53
printf("%d\n",-parent[find(0)]);
54
}
55
return 0;
56
}
posted @
2009-04-22 20:16 wyiu 阅读(186) |
评论 (0) |
编辑 收藏
1
#include<iostream>
2
using namespace std;
3
#define MAXN 2000
4
#define string1 "Scenario #"
5
#define string2 "Suspicious bugs found!"
6
#define string3 "No suspicious bugs found!"
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
int parent[MAXN+1];
9
int rank[MAXN+1];
10
int dif[MAXN+1];
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
void Init(int n=MAXN)
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
14
int i;
15
for(i=0;i<=n;i++)
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
17
rank[i]=0;
18
parent[i]=i;
19
dif[i]=-1;
20
}
21
}
22![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
23
int find(int x)
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
25
26
if(parent[x]!=x)
27
parent[x]=find(parent[x]);
28
return parent[x];
29
}
30![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
31
int merge_set(int a,int b)
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
33
if(a==-1) return b;
34
if(b==-1) return a;
35
if(rank[a]>rank[b])
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
37
parent[b]=a;
38
return a;
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
40
parent[a]=b;
41
if(rank[a]==rank[b])
42
rank[b]++;
43
return b;
44
}
45
}
46
void Union(int a,int b)
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
48
int root1=find(a),
49
root2=find(b),
50
da=merge_set(dif[root1],root2), //b的新根
51
db=merge_set(root1,dif[root2]); //a的新根
52
dif[db]=da;
53
dif[da]=db;
54
}
55![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
56![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
57
int main()
58![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
59
int S,N,M,a,b,i;
60
bool flag;
61
62
scanf("%d",&S);
63
for(i=1;i<=S;i++)
64![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
65
scanf("%d%d",&N,&M);
66
Init(N);
67
flag=true;
68
while(M--)
69![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
70
scanf("%d%d",&a,&b);
71
Union(a,b);
72
if(find(a)==find(b)) flag=false;
73
}
74
if(flag==false)
75
printf("%s%d:\n%s\n\n",string1,i,string2);
76
else printf("%s%d:\n%s\n\n",string1,i,string3);
77
78
}
79
return 0;
80
}
81![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2009-04-21 16:42 wyiu 阅读(151) |
评论 (0) |
编辑 收藏
1
#include<iostream>
2
using namespace std;
3
#define MAXN 100000
4
#define string1 "Not sure yet."
5
#define string2 "In different gangs."
6
#define string3 "In the same gang."
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
int parent[MAXN+1];
9
int rank[MAXN+1];
10
int dif[MAXN+1];
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
void Init(int n=MAXN)
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
14
int i;
15
for(i=0;i<=n;i++)
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
17
rank[i]=0;
18
parent[i]=i;
19
dif[i]=-1;
20
}
21
}
22![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
23
int find(int x)
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
25
26
if(parent[x]!=x)
27
parent[x]=find(parent[x]);
28
return parent[x];
29
}
30![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
31
int merge_set(int a,int b)
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
33
if(a==-1) return b;
34
if(b==-1) return a;
35
if(rank[a]>rank[b])
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
37
parent[b]=a;
38
return a;
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
40
parent[a]=b;
41
if(rank[a]==rank[b])
42
rank[b]++;
43
return b;
44
}
45
}
46
void Union(int a,int b)
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
48
int root1=find(a),
49
root2=find(b),
50
da=merge_set(dif[root1],root2), //b的新根
51
db=merge_set(root1,dif[root2]); //a的新根
52
dif[db]=da;
53
dif[da]=db;
54
}
55![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
56
int main()
57![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
58
int T,N,M,a,b,i;
59
char c;
60
scanf("%d",&T);
61
while(T--)
62![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
63
//memset(parent,0,sizeof(parent));
64
scanf("%d%d",&N,&M);
65
Init(N);
66
while(M--)
67![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
68
scanf(" %c%d%d",&c,&a,&b);
69
if(c=='A')
70![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
71
a=find(a);
72
b=find(b);
73
if(a==b)
74
printf("%s\n",string3);
75![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
76
if(a==dif[b])
77
printf("%s\n",string2);
78
else printf("%s\n",string1);
79
}
80
}
81
else
82![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
83
Union(a,b);
84
}
85
}
86
87
}
88
return 0;
89
}
90![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2009-04-21 16:36 wyiu 阅读(137) |
评论 (0) |
编辑 收藏
http://hi.baidu.com/fandywang_jlu/blog/item/b49e40893ddbb0b00f244485.html并查集:(union-find sets)是一种简单的用途广泛的集合. 并查集是若干个不相交集合,能够实现较快的合并和判断元素所在集合的操作,应用很多,如其求无向图的连通分量个数、最小公共祖先、带限制的作业排序,还有最完美的应用:实现Kruskar算法求最小生成树。其实,这一部分《算法导论》讲的很精炼。
一般采取树形结构来存储并查集,在合并操作时可以利用树的节点数(加权规则)或者利用一个rank数组来存储集合的深度下界--启发式函数,在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集,空间复杂度为O(N),建立一个集合的时间复杂度为O(1),N次合并M查找的时间复杂度为O(M Alpha(N)),这里Alpha是Ackerman函数的某个反函数,在很大的范围内这个函数的值可以看成是不大于4的,所以并查集的操作可以看作是线性的。
它支持以下三种操作:
-Union (Root1, Root2) //合并操作;把子集合Root2和子集合Root1合并.要求:Root1和 Root2互不相交,否则不执行操作.
-Find (x) //搜索操作;搜索元素x所在的集合,并返回该集合的名字--根节点.
-UFSets (s) //构造函数。将并查集中s个元素初始化为s个只有一个单元素的子集合.
-对于并查集来说,每个集合用一棵树表示。
-集合中每个元素的元素名分别存放在树的结点中,此外,树的每一个结点还有一个指向其双亲结点的指针。
-为简化讨论,忽略实际的集合名,仅用表示集合的树的根来标识集合。
以下给出我的两种实现:
1
//Abstract: UFSet
2![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
3
//Author:Lifeng Wang (Fandywang)
4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
// Model One 与Model 2 路径压缩方式不同,合并标准不同
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10
const int MAXSIZE = 500010;
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
int rank[MAXSIZE]; // 节点高度的上界
13![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
14
int parent[MAXSIZE]; // 根节点
15![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int FindSet(int x)
{// 查找+递归的路径压缩
17![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
18
if( x != parent[x] ) parent[x] = FindSet(parent[x]);
19![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
20
return parent[x];
21![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
22
}
23![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Union(int root1, int root2)
{
25![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
26
int x = FindSet(root1), y = FindSet(root2);
27![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
28
if( x == y ) return ;
29![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
30
if( rank[x] > rank[y] ) parent[y] = x;
31![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
33![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
34
parent[x] = y;
35![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
36
if( rank[x] == rank[y] ) ++rank[y];
37![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
38
}
39![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
40
}
41![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Initi(void)
{
43![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
44
memset(rank, 0, sizeof(rank));
45![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
46
for( int i=0; i < MAXSIZE; ++i ) parent[i] = i;
47![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
48
}
49![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
50![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
51![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
52![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
53
// Model Two
54![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
55
const int MAXSIZE = 30001;
56![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
57
int pre[MAXSIZE]; //根节点i,pre[i] = -num,其中num是该树的节点数目;
58![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
59
//非根节点j,pre[j] = k,其中k是j的父节点
60![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
61![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int Find(int x)
{//查找+非递归的路径压缩
62![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
63
int p = x;
64![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
65
while( pre[p] > 0 ) p = pre[p];
66![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
67![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while( x != p )
{
68![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
69
int temp = pre[x]; pre[x] = p; x = temp;
70![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
71
}
72![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
73
return x;
74![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
75
}
76![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Union(int r1, int r2)
{
78![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
79
int a = Find(r1); int b = Find(r2);
80![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
81
if( a == b ) return ;
82![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
83
//加权规则合并
84![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
85![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if( pre[a] < pre[b] )
{
86![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
87
pre[a] += pre[b]; pre[b] = a;
88![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
89
}
90![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
91![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
92![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
93
pre[b] += pre[a]; pre[a] = b;
94![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
95
}
96![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
97
}
98![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
99
void Initi(void)
100![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
101![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
102![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
103
for( int i=0; i < N; ++i ) pre[i] = -1;
104![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
105
}
106![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
107![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
并查集的一些题目和我的相关解题报告:
POJ 1611 The Suspects 最基础的并查集
POJ 2524 Ubiquitous Religions 最基本的并查集
POJ 1182 食物链 并查集的拓展
注意: 只有一组数据;
要充分利用题意所给条件:有三类动物A,B,C,这三类动物的食物链
构成了有趣的环形。A吃B, B吃C,C吃A。也就是说:只有三个group
POJ 2492 A Bug's Life 并查集的拓展
法一:深度优先遍历
每次遍历记录下该点是男还是女,只有:男-〉女,女-〉男满足,否则,找到同性恋,结束程序。
法二:二分图匹配
法三:并查集的拓展:和1182很像,只不过这里就有两组,而1182是三组,1611无限制
POJ 1861 Network == zju_1542 并查集+自定义排序+贪心求"最小生成树"
答案不唯一,不过在ZOJ上用QSORT()和SORT()都能过,在POJ上只有SORT()才能过...
POJ 1703 Find them, Catch them 并查集的拓展
这个和POJ 2492 A Bug's Life很像,就是把代码稍微修改了一下就AC了!
注意:And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. 就是说只有两个组。
POJ 2236 Wireless Network 并查集的应用
需要注意的地方:1、并查集;2、N的范围,可以等于1001;3、从N+1行开始,第一个输入的可以是字符串。
POJ 1988 Cube Stacking 并查集很好的应用
1、与 银河英雄传说==NOI2002 Galaxy一样;2、增加了一个数组behind[x],记录战舰x在列中的相对位置;3、详细解题报告见银河英雄传说。
JOJ 1905 Freckles == POJ 2560 最小生成树
法一:Prim算法;法二:并查集实现Kruskar算法求最小生成树
JOJ 1966 Super Market III == PKU 1456 Supermarket 带限制的作业排序问题(贪心+并查集)
提高题目:
POJ 2912 Rochambeau
POJ 1733 Parity game
POJ 1308 Is It A Tree?
posted @
2009-04-21 14:56 wyiu 阅读(165) |
评论 (0) |
编辑 收藏