ZOJ3261-Connections in Galaxy War-（逆向并查集+离线处理）

题意：

1.有n个星球，每个星球有一个编号（1-n）和一个能量值。

2.一开始将某些星球连通。

3.开战后有很多个操作，查询某个星球能找谁求救或者摧毁两颗星球之间的连通路径，使其不能连通。如果连通则可以相互求救，求救的对象要求能量比自己大并且在连通的星球中能量最大，如果能量最大的星球有多个，则找编号小的。

解题：

1.用并查集连通星球，把能量大的作为根节点，如果能量相同则把编号小的作为根节点，方便查询求救对象。

2.并查集没有断开的操作，把末态作为起始状态逆推。保存一开始的连通路径和开战后摧毁的连通路径，战争结束的状态作为起始状态，不连通被摧毁的连通路径。

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<math.h>
  6 #include<string>
  7 #include<map>
  8 #include<queue>
  9 #include<stack>
 10 #include<set>
 11 #define ll long long
 12 #define inf 0x3f3f3f3f
 13 using namespace std;
 14 
 15 int n,m,x,y,q;
 16 int par[10005];///父亲
 17 map<int,bool>mp;
 18 int ans[50086];
 19 struct star
 20 {
 21     int id;///编号
 22     int val;///能量值
 23 };star s[10005];
 24 
 25 struct edge
 26 {
 27     int x;
 28     int y;
 29 };edge e[20086];
 30 
 31 struct query
 32 {
 33     char s[10];
 34     int x,y;
 35 
 36 };query que[50086];
 37 
 38 
 39 
 40 int find(int a)
 41 {
 42     if( par[a]==a )
 43         return a;
 44     return par[a]=find(par[a]);
 45 }
 46 
 47 void unit(int a,int b)
 48 {
 49     int aa=find(a);
 50     int bb=find(b);
 51     if(aa!=bb)
 52     {
 53         if( s[aa].val==s[bb].val )///相同能量值
 54         {
 55             if( s[aa].id<s[bb].id )///编号小的做根节点
 56                 par[bb]=aa;
 57             else
 58                 par[aa]=bb;
 59         }
 60         else if( s[aa].val<s[bb].val )///能量值大的作为根节点
 61             par[aa]=bb;
 62         else
 63             par[bb]=aa;
 64     }
 65 }
 66 
 67 int main()
 68 {
 69     bool first=true;
 70     while(scanf("%d",&n)!=EOF)///行星数量
 71     {
 72         if(first)///第一次进来变为false，以后每次都要打印空行
 73             first=false;
 74         else printf("
");
 75         mp.clear();
 76         memset(ans,inf,sizeof(ans));
 77         for(int i=0;i<n;i++)///能量值
 78         {
 79             scanf("%d",&s[i].val);
 80             s[i].id=i;
 81             par[i]=i;
 82         }
 83         scanf("%d",&m);///连通边
 84         for(int i=0;i<m;i++)
 85         {
 86             scanf("%d%d",&x,&y);
 87             if(x>y)///保证x<y
 88                 swap(x,y);
 89             e[i].x=x;
 90             e[i].y=y;///存连通边
 91             mp[ x*10000+y ]=false;///没被毁掉
 92         }
 93         scanf("%d",&q);///查询
 94         for(int i=0;i<q;i++)
 95         {
 96             getchar();
 97             scanf("%s",que[i].s);
 98             if(que[i].s[0]=='q')
 99                 scanf("%d",&que[i].x);
100             else
101             {
102                 scanf("%d %d",&x,&y);
103                 if(x>y)///保证x<y
104                     swap(x,y);
105                 que[i].x=x;
106                 que[i].y=y;
107                 mp[ x*10000+y ]=true;///被毁掉
108             }
109         }
110         ///离线处理
111         for(int i=0;i<m;i++)///把没被毁掉的边的末态作为起始态，逆推
112         {
113             x=e[i].x;
114             y=e[i].y;
115             if( !mp[ x*10000+y ] )
116                 unit(x,y);
117         }
118         ///逆推,保存对应的答案
119         for(int i=q-1;i>=0;i--)
120         {
121             if( que[i].s[0]=='q' )
122             {
123                 x=find(que[i].x);///连通星球中 能量最大的 根星球
124                 if( s[x].val>s[ que[i].x ].val )
125                     ans[i]=s[x].id;
126                 else
127                     ans[i]=-1;
128             }
129             else
130                 unit( que[i].x,que[i].y );
131         }
132         ///顺序输出答案
133         for(int i=0;i<q;i++)
134         {
135             if(ans[i]!=inf)
136                 printf("%d
",ans[i]);
137         }
138     }
139     return 0;
140 }

ZOJ3261-Connections in Galaxy War-（逆向并查集+离线处理）

相关推荐