Codeforces 1296F Berland Beauty

1————2————3————4————5————6

1->3 2

2->4 3

3->5 3

4->6 5

题目说 (u->v w)途中所有边 e1,e2,e3,...en∈E,满足任意|ex| >= w(ex∈E),

上面图中  3->5 3    4->6 5,说明(|e(4->5)| >= 3 && |e(4->5)| >= 5)  ==>  |e(4->5)| >= 5。

通过这个想法,我们可以把边以(w)排序,大到小,先染色w大的,w小的不能去重新染色w大的,只能

染色未被染色的部分或者w相同的部分,例如(2->4)(3->5)w都是3,那么,如果某次(u->v w)无法染色,

说明就是"-1".

用了lca去优化(u->v)的寻路过程。

1 #include <iostream> 2 #include <algorithm> 3 #include <map> 4 #include <vector> 5 #include <cstdio> 6 using namespace std; 7 8 const int N = (int)5e3+10,INF = (int)1e6; 9 struct node{ 10 int to,nxt; 11 }e[N<<1]; 12 struct Info{ 13 int u,v,w; 14 bool friend operator<(const Info& a,const Info& b){ 15 return a.w > b.w; 16 } 17 }info[N]; 18 map<pair<int,int>, int > mp;// 19 pair<int,int > pii; 20 vector<pair<int,int > > vii; 21 int n,m,u,v,w,tot,tim; 22 int head[N],dfn[N],fa[N]; 23 24 inline void add(int u,int v){ 25 e[tot].to = v; e[tot].nxt = head[u]; head[u] = tot++; 26 e[tot].to = u; e[tot].nxt = head[v]; head[v] = tot++; 27 } 28 29 void dfs_dfn(int now,int pre){ 30 dfn[now] = ++tim; 31 for(int o = head[now]; ~o; o = e[o].nxt){ 32 if(e[o].to == pre) continue; 33 dfs_dfn(e[o].to,now); 34 } 35 } 36 37 void dfs_mp(int now,int pre){ 38 for(int o = head[now]; ~o; o = e[o].nxt){ 39 int to = e[o].to; 40 if(to == pre) continue; 41 fa[dfn[to]] = dfn[now]; 42 mp[make_pair(dfn[now],dfn[to])] = INF;//初始化边INF,把边的两点转化为dfn,总是以dnf小的在first位置 43                        //输出答案的时候,通过dfn[u],dfn[v]去得到这条边 44 dfs_mp(e[o].to,now); 45 } 46 } 47 48 void show(){ 49 for(int i = 1; i <= n; ++i) 50 printf("u = %d dfn = %d\n",i,dfn[i]); 51 for(int i = 1; i <= m; ++i) cout << info[i].w << endl; 52 for(int i = 1; i <= n; ++i) 53 printf("u = %d fa = %d\n",i,fa[dfn[i]]); 54 } 55 56 bool lca(int u,int v,int w){ 57 int u_dfn = dfn[u],v_dfn = dfn[v],tmp_w; 58 bool ok = 0; 59 while(u_dfn != v_dfn){ 60 while(u_dfn > v_dfn){ 61 pii.first = fa[u_dfn]; pii.second = u_dfn; 62 tmp_w = mp[pii]; 63 if(tmp_w == INF || tmp_w == w){//未被染色,或者w相同 64 ok = 1; 65 mp[pii] = w; 66 } 67 u_dfn = pii.first; 68 } 69 while(u_dfn < v_dfn){ 70 pii.first = fa[v_dfn]; pii.second = v_dfn; 71 tmp_w = mp[pii]; 72 if(tmp_w == INF || tmp_w == w){ 73 ok = 1; 74 mp[pii] = w; 75 } 76 v_dfn = pii.first; 77 } 78 } 79 return ok; 80 } 81 82 void solve(){ 83 for(int i = 1; i <= n; ++i) head[i] = -1; tot = 0; 84 for(int i = 1; i <= n-1; ++i){ 85 scanf("%d%d",&u,&v); 86 vii.push_back(make_pair(u,v)); 87 add(u,v); 88 } 89 dfs_dfn(1,0);//初始化dfn序 90 fa[1] = 1; 91 dfs_mp(1,0);//初始化边长和fa[]数组 92 scanf("%d",&m); 93 for(int i = 1; i <= m; ++i){ 94 scanf("%d%d%d",&info[i].u,&info[i].v,&info[i].w); 95 } 96 97 sort(info+1,info+1+m);//边按W排序 98 for(int i = 1; i <= m; ++i){ 99 if(lca(info[i].u,info[i].v,info[i].w)) continue; 100 printf("-1\n"); return; 101 } 102 int l = vii.size(); 103 int dfn1,dfn2; 104 for(int i = 0; i < l; ++i){ 105 dfn1 = dfn[vii[i].first]; 106 dfn2 = dfn[vii[i].second]; 107 if(dfn1 > dfn2) swap(dfn1,dfn2); 108 pii.first = dfn1; pii.second = dfn2; 109 printf("%d ",mp[pii]); 110 }cout << endl; 111 } 112 113 int main(){ 114 115 scanf("%d",&n); 116 solve(); 117 118 return 0; 119 }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyzgfz.html