题意:给定两棵树,每次能够连接一棵树的一条边,并且删除当钱形成环的其中一条边,问经过最少多少次能够使得两棵树的边是一样的。
题解:没想到什么高级的东西,就模拟吧。第一棵树不动,在第一棵树中存在 && 在第二棵树中不存在的边的个数就是需要修改的次数,每次加在第一棵树中
存在 && 在第二棵树中不存咋的一条边,这样能保证在环中一定有一条边在第一棵树中不存在,模拟之即可。
Sure原创,转载请注明出处
#include <iostream> #include <cstdio> #include <memory.h> using namespace std; const int maxn = 2002; struct EE { int u,v; }l[maxn]; struct node { int v; int next; }edge[maxn << 2]; int head[maxn],stack[maxn]; bool valid[maxn][maxn],goal[maxn][maxn]; int n,idx,sum,top; void init() { memset(valid,false,sizeof(valid)); memset(goal,false,sizeof(goal)); memset(head,-1,sizeof(head)); idx = sum = 0; return; } void addedge(int u,int v) { edge[idx].v = v; edge[idx].next = head[u]; head[u] = idx++; edge[idx].v = u; edge[idx].next = head[v]; head[v] = idx++; return; } void read() { for(int i=0;i<n-1;i++) { scanf("%d %d",&l[i].u,&l[i].v); goal[l[i].u][l[i].v] = goal[l[i].v][l[i].u] = true; } int u,v; for(int i=1;i<n;i++) { scanf("%d %d",&u,&v); addedge(u,v); valid[u][v] = valid[v][u] = true; } for(int i=0;i<n-1;i++) { if(valid[l[i].u][l[i].v] == false) { sum++; } } return; } bool dfs(int st,int pre,int y) { if(st == y) return true; for(int i=head[st];i != -1;i=edge[i].next) { if(edge[i].v == pre || valid[st][edge[i].v] == false) continue; stack[top++] = i; if(dfs(edge[i].v , st , y)) return true; else top--; } return false; } void solve() { printf("%d\n",sum); int r = 0; for(int i=0;i<sum;i++) { while(r < n-1 && valid[l[r].u][l[r].v]) r++; printf("2 %d %d",l[r].u , l[r].v); top = 0; dfs(l[r].u , 0 , l[r].v); for(int j=0;j<top;j++) { int u = edge[stack[j]^1].v; int v = edge[stack[j]].v; if(goal[u][v] == false) { valid[u][v] = valid[v][u] = false; printf(" %d %d\n",u,v); break; } } addedge(l[r].u , l[r].v); valid[l[r].u][l[r].v] = valid[l[r].v][l[r].u] = true; r++; } return; } int main() { while(~scanf("%d",&n)) { init(); read(); solve(); } return 0; }