网址如下:
测,这题差点让我去世
用了一堆方法来做
后面现学了并查集,用了并查集来做,因为缩短路径的方法不好,还是超时了
后面换了一种缩短路径的方法
先上代码
解法一(TLE)
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 100001;
int kase[maxn], N, M;
vector<int> G[maxn];
bool vis[maxn];
void init(void){
for(int i = 1; i <= N; i++) G[i].clear();
memset(kase, -1, sizeof(kase));
}
void chg(int idx){
vis[idx] = true;
for(int i = 0; i < G[idx].size(); i++) if(!vis[G[idx][i]]) chg(G[idx][i]);
kase[idx] = !kase[idx];
}
void fill(int idx, int b){
vis[idx] = true;
if(vis[b]) return;
for(int i = 0; i < G[idx].size(); i++) if(!vis[G[idx][i]]) fill(G[idx][i], b);
}
void distinguish(int a, int b){
if(kase[a] == -1 && kase[b] == -1){kase[a] = 0; kase[b] = 1;}
else if(kase[a] == -1){kase[a] = !kase[b];}
else if(kase[b] == -1){kase[b] = !kase[a];}
else if(kase[a] == kase[b]){memset(vis, 0, sizeof(vis)); chg(a);}
G[a].push_back(b); G[b].push_back(a);
}
void ans(int a, int b){
if(kase[a] == -1 || kase[b] == -1) printf("Not sure yet.\n");
else{
memset(vis, 0, sizeof(vis));
fill(a, b);
if(vis[b]){
if(kase[a] == kase[b]) printf("In the same gang.\n");
else printf("In different gangs.\n");
}
else printf("Not sure yet.\n");
}
}
int main(void)
{
int T; scanf("%d", &T);
while(T--){
scanf("%d%d", &N, &M);
init();
while(M--){
getchar(); char c = getchar();
int a, b; scanf("%d%d", &a, &b);
if(c == 'A') ans(a, b);
else distinguish(a, b);
}
}
return 0;
}
思路
我就是根据已有的情报直接假设哪几个案件是哪个团伙干的
只需要维护这几个案件的关系满足情报就行
但是因为是随意假设的,所以会出现假设完的两个案件与情报不符
这就要改变其中一个案件(0变1或1变0)
或者说“案件图”
因为D a b把这一片案件连起来了
所以都要改
同时,还有一种意外情况,两个案件不在同一个“案件图”上,案件都不为-1(代表未定义)
就需要事先判断二者在同一个“案件图”上
总结
我们需要做的:记录“情报图”,并维护案件的关系与情报相符
两个案件可以判断关系的前提条件:都定义了,且在同一个“情报图”上
但是TLE了
解法二(TLE)
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100001;
int kase[maxn], N, M;
int color[maxn];
int newcolor;
void init(void){
memset(kase, -1, sizeof(kase));
memset(color, 0, sizeof(color));
newcolor = 1;
}
void paint(int Dst, int Src){
for(int i = 1; i <= N; i++) if(color[i] == Src) color[i] = Dst;
}
void distinguish(int a, int b){
if(kase[a] == -1 && kase[b] == -1){kase[a] = 0; kase[b] = 1; color[a] = color[b] = newcolor++;}
else if(kase[a] == -1){kase[a] = !kase[b]; color[a] = color[b];}
else if(kase[b] == -1){kase[b] = !kase[a]; color[b] = color[a];}
else if(kase[a] == kase[b]){paint(color[a], color[b]);}
}
void ans(int a, int b){
if(kase[a] == -1 || kase[b] == -1) printf("Not sure yet.\n");
else{
if(color[a] == color[b]){
if(kase[a] == kase[b]) printf("In the same gang.\n");
else printf("In different gangs.\n");
}
else printf("Not sure yet.\n");
}
}
int main(void)
{
int T; scanf("%d", &T);
while(T--){
scanf("%d%d", &N, &M);
init();
while(M--){
getchar(); char c = getchar();
int a, b; scanf("%d%d", &a, &b);
if(c == 'A') ans(a, b);
else distinguish(a, b);
}
}
return 0;
}
思路
根据上面我所说的,我只是把一个“案件图”涂上了相同的颜色,来标记这些案件属于同一个“案件图”。这样,每次出现两个案件不在同一个“案件图”上,案件都不为-1(代表未定义)的情况,合并“案件图”就只需要把一个“案件图”的颜色涂成另一个“案件图”的
就不需要解法一的vector来记录图的结点之间的联系,减少了内存操作
但是每次重涂就需要遍历所有的案件
重涂数量多了就完蛋
最后还是TLE
解法三(TLE)
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100001;
int kase[maxn], N, M;
int color[maxn];
int head[maxn], next[maxn];
int newcolor;
void init(void){
memset(kase, -1, sizeof(kase));
memset(color, 0, sizeof(color));
memset(head, 0, sizeof(head));
memset(next, 0, sizeof(next));
newcolor = 1;
}
inline void list_insert(int idx, int color){
next[idx] = head[color];
head[color] = idx;
}
void paint(int Dst, int Src){
for(int i = head[Src]; i; i = next[i]){color[i] = Dst; kase[i] = !kase[i]; list_insert(i, Dst);}
}
void distinguish(int a, int b){
if(kase[a] == -1 && kase[b] == -1){kase[a] = 0; kase[b] = 1; color[a] = color[b] = newcolor; list_insert(a, newcolor); list_insert(b, newcolor++);}
else if(kase[a] == -1){kase[a] = !kase[b]; color[a] = color[b]; list_insert(a, color[b]);}
else if(kase[b] == -1){kase[b] = !kase[a]; color[b] = color[a]; list_insert(b, color[a]);}
else if(kase[a] == kase[b]){paint(color[a], color[b]);}
}
void ans(int a, int b){
if(kase[a] == -1 || kase[b] == -1) printf("Not sure yet.\n");
else{
if(color[a] == color[b]){
if(kase[a] == kase[b]) printf("In the same gang.\n");
else printf("In different gangs.\n");
}
else printf("Not sure yet.\n");
}
}
int main(void)
{
int T; scanf("%d", &T);
while(T--){
scanf("%d%d", &N, &M);
init();
while(M--){
getchar(); char c = getchar();
int a, b; scanf("%d%d", &a, &b);
if(c == 'A') ans(a, b);
else distinguish(a, b);
}
}
return 0;
}
思路
那优化就很简单了,既然每次重涂都需要遍历所有元素,那么我建立链表,将需要改变的案件记录起来就行了
但是还是TLE,因为数据太大了
解法四(TLE)
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100001;
int condition[maxn], N, M;
int parent[maxn], rank[maxn];
int newcolor;
void init(void){
memset(condition, 0, sizeof(condition));
memset(rank, 1, sizeof(rank));
for(int i = 1; i <= N; i++) parent[i] = i;
newcolor = 1;
}
int find(int idx){
if(parent[idx] == idx) return idx;
return find(parent[idx]);
}
int get_relation(int idx){
if(parent[idx] == idx) return 0;
return get_relation(parent[idx]) ^ condition[idx];
}
void join(int idx1, int idx2){
int prt1 = find(idx1), prt2 = find(idx2);
if(prt1 == prt2) return;
int r1 = get_relation(idx1), r2 = get_relation(idx2);
if(rank[prt1] < rank[prt2]){parent[prt1] = prt2; condition[prt1] = !(r1 ^ r2);}
else{
if(rank[prt1] == rank[prt2]) rank[prt2]++;
parent[prt2] = prt1; condition[prt2] = !(r1 ^ r2);
}
}
void ans(int a, int b){
int prt1 = find(a), prt2 = find(b);
if(prt1 != prt2) printf("Not sure yet.\n");
else{
int r1 = get_relation(a), r2 = get_relation(b);
if(r1 == r2) printf("In the same gang.\n");
else printf("In different gangs\n");
}
}
int main(void)
{
int T; scanf("%d", &T);
while(T--){
scanf("%d%d", &N, &M);
init();
while(M--){
getchar(); char c = getchar();
int a, b; scanf("%d%d", &a, &b);
if(c == 'A') ans(a, b);
else join(a, b);
}
}
return 0;
}
思路
考虑到上面的图的特点:不相交,并且需要合并,还要查找元素的关系
然后我去学了并查集
可以看看这篇博客:【算法与数据结构】—— 并查集-CSDN博客
讲的非常简单易懂
然后我用了并查集,并使用了上面那篇博客里面讲的第二种的缩短路径的方法
其中condition记录案件和父案件的关系
parent和rank的意义见上面那篇博客
然后
还是TLE
我差点裂了
解法五(AC)
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100001;
int condition[maxn], N, M;
int parent[maxn];
int newcolor;
void init(void){
memset(condition, 0, sizeof(condition));
for(int i = 1; i <= N; i++) parent[i] = i;
}
int find(int idx){
if(parent[idx] == idx) return idx;
int par = parent[idx];
while(parent[par] != par){
condition[idx] = condition[idx] ^ condition[par];
parent[idx] = parent[par];
par = parent[idx];
}
return find(parent[idx]);
}
void join(int idx1, int idx2){
int prt1 = find(idx1), prt2 = find(idx2);
if(prt1 == prt2) return;
parent[prt1] = prt2;
condition[prt1] = !(condition[idx1] ^ condition[idx2]);
}
void ans(int a, int b){
int prt1 = find(a), prt2 = find(b);
if(prt1 != prt2) printf("Not sure yet.\n");
else{
if(condition[a] == condition[b]) printf("In the same gang.\n");
else printf("In different gangs.\n");
}
}
int main(void)
{
int T; scanf("%d", &T);
while(T--){
scanf("%d%d", &N, &M);
init();
while(M--){
getchar(); char c = getchar();
int a, b; scanf("%d%d", &a, &b);
if(c == 'A') ans(a, b);
else join(a, b);
}
}
return 0;
}
思路
最后就是这玩意了
用到了上述博客提到的缩短路径的第一种方法
condition的意义和解法四的一样
最后AC了