HNOI 2019 D2T1

Imakf

2019-04-08 17:50:20

Solution

~~神仙dp题,考场爆0只有我了~~ # 解法 myy出的,搬一下**他的原话如下** 30分的DP就是dp[i][j]表示i到j是否存在一条合法的路径,转移就是枚举i的边和j的边。总复杂度是$O(m^2)$。 考虑减少边数。我们把一种标号单独拿出来,只考虑连接同一种标号的两个点的边。 对于一个连通块,如果它是二分图,那么我们仅保留一棵生成树答案也不会变。这是因为我们容易发现这个连通块之内的转移仍然可以实现(只要另一边在两个点内来回走即可)。如果它不是二分图,我们可以加一个自环。 我们考虑连接不同标号的边,只把这些边拿出来我们也可以形成若干个连通块。对于每个连通块, 根据同样的道理我们保留一棵生成树即可(注意这个时候连通块一定都是二分图)。 这样总边数不超过$2n-2$,用30分DP的思路可以做到$O(n^2)$并且通过本题。 ---- 所以为什么不是二分图的时候可以加自环呢?仔细想想,如果图不是二分图,就说明图中一定有长度为奇数的环。那么在这边可以一直来回转圈,另一边如果也有奇数环,那么显然可以匹配,如果另一边是二分图,那么显然我们可以在这一边转上几圈,让长度变成偶数,依然可以转移QAQ 如果不懂的话可以自己手造数据的QAQ,个人认为比较好理解 于是就变成了$kruskal$ ```cpp #include<cstdio> #include<cstring> #include<ctime> #include<cstdlib> #include<algorithm> #include<queue> #define rg register #define il inline #define MX (5000 + 65) #define M_MX (500000 + 5) int cs ,cd; struct ip{ int u ,v; }same[M_MX] ,diff[M_MX]; int color[MX]; namespace FS{ //forward_star 前向星 int head[MX] ,tot; struct edge{ int node ,next; }h[M_MX << 1]; il void addedge(int u ,int v){ h[++tot].next = head[u]; head[u] = tot; h[tot].node = v; } } int n ,m ,q; int fa[MX]; void init(int upper){ for(rg int i = 1 ; i <= upper ; ++i) fa[i] = i; using namespace FS; memset(FS::head ,0 ,sizeof(head)); memset(h ,0 ,sizeof(h)); tot = 0; } int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);} void link(int x ,int y){fa[find(x)] = find(y);} int vis[MX][MX] ,DP[MX][MX]; namespace MST{ //Minimum Spanning Tree 最小生成树 int head[MX] ,tot; FS::edge h[M_MX << 1]; void addedge(int u ,int v){ h[++tot].next = head[u]; head[u] = tot; h[tot].node = v; }int Tag[MX]; bool check2fen(int x ,int tag){ if(Tag[x]) return Tag[x] == tag; Tag[x] = tag; for(rg int i = FS::head[x] ; i ; i = FS::h[i].next){ int d = FS::h[i].node; if(!check2fen(d ,tag == 1 ? 2 : 1)) return false; }return true; } void kruskal(int type){ if(type == 1){ //单独拿出连接同种编号的 for(rg int i = 1 ; i <= n ; ++i) Tag[i] = false; init(n); int cnt = 0; for(rg int i = 1 ; i <= cs ; ++i){ FS::addedge(same[i].u ,same[i].v); FS::addedge(same[i].v ,same[i].u); } for(rg int i = 1 ; i <= cs ; ++i){ if(find(same[i].u) != find(same[i].v)){ LST::addedge(same[i].u ,same[i].v); LST::addedge(same[i].v ,same[i].u); link(same[i].u ,same[i].v); ++cnt; } } for(rg int i = 1 ; i <= n ; ++i){ if(!Tag[i]){ if(!check2fen(i ,1)) LST::addedge(i ,i); } } } else{//单独拿出连接不同种编号的 init(n); for(rg int i = 1 ; i <= n ; ++i) Tag[i] = false; int cnt = 0; for(rg int i = 1 ; i <= cd ; ++i){ FS::addedge(diff[i].u ,diff[i].v); FS::addedge(diff[i].v ,diff[i].u); } for(rg int i = 1 ; i <= cd ; ++i){ if(find(diff[i].u) != find(diff[i].v)){ LST::addedge(diff[i].u ,diff[i].v); LST::addedge(diff[i].v ,diff[i].u); link(diff[i].u ,diff[i].v); ++cnt; } } for(rg int i = 1 ; i <= n ; ++i){ if(!Tag[i]){ if(!check2fen(i ,1)) LST::addedge(i ,i); } } } } }using namespace MST; void dp(){ //大力转移,因为本题有O2,可以放心用STL std::queue<int> q1 ,q2; for(rg int i = 1 ; i <= n ; ++i){ vis[i][i] = true; DP[i][i] = true; q1.push(i) ,q2.push(i); for(rg int j = head[i] ,d ; j ; j = h[j].next){ d = h[j].node; vis[i][d] = vis[d][i] = true; if(color[i] != color[d]) continue; DP[i][d] = DP[d][i] = true; q1.push(i) ,q2.push(d); } } while(!q1.empty()){ int x = q1.front() ,y = q2.front(); q1.pop() ,q2.pop(); for(rg int i = head[x] ; i ; i = h[i].next){ for(rg int j = head[y] ; j ; j = h[j].next){ if(!vis[h[i].node][h[j].node] && color[h[i].node] == color[h[j].node]){ DP[h[i].node][h[j].node] = DP[h[j].node][h[i].node] = true; q1.push(h[i].node) ,q2.push(h[j].node); }vis[h[i].node][h[j].node] = vis[h[j].node][h[i].node] = true; } } } } int main(){ scanf("%d%d%d" ,&n ,&m ,&q); for(rg int i = 1 ; i <= n ; ++i){ scanf("%1d" ,color + i); } for(rg int i = 1 ,u ,v ; i <= m ; ++i){ scanf("%d%d" ,&u ,&v); FS::addedge(u ,v); FS::addedge(v ,u); if(color[u] ^ color[v]) diff[++cd] = (ip){u ,v}; else same[++cs] = (ip){u ,v}; } using namespace MST; kruskal(1); kruskal(2); //outedge(); dp(); for(rg int i = 1 ,u ,v ; i <= q ; ++i){ scanf("%d%d" ,&u ,&v); if(DP[u][v] || DP[v][u]) puts("YES"); else puts("NO"); } return 0; } ```