首页 > 代码库 > BestCoder Round #1 1001 && 1002 hdu 4857 4858
BestCoder Round #1 1001 && 1002 hdu 4857 4858
hdu 4857 逃生
第一题是拓扑排序，不是按照字典序最小输出，而是要使较小的数排在最前面。。赛后弄了好久，才比较明白，我一直以为 反向建图，i从1到n，开始深搜dfs( i )，对i点的边，由小到大继续搜一下，同时标记搜过的数，搜过之后就不再搜，搜到底之后ans[cnt++] = u;这样顺序输出就是答案，后来经过超哥指点，才明白深搜贪心是错的。只有 反向建图，用优先队列把较大的数尽量排在前面，然后反序输出才是正解。。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std; 11 12 #define mnx 104000 13 #define ll long long 14 #define inf 0x3f3f3f3f 15 #define lson l, m, rt << 1 16 #define rson m+1, r, rt << 1 | 1 17 18 vector<int> vet[mnx]; 19 int cnt, ans[mnx], vis[mnx]; 20 int main(){ 21 int cas; 22 scanf( "%d", &cas ); 23 while( cas-- ){ 24 for( int i = 0; i < mnx; i++ ){ 25 vet[i].clear(); 26 } 27 memset( vis, 0, sizeof(vis) ); 28 cnt = 0; 29 int n, m; 30 scanf( "%d%d", &n, &m ); 31 for( int i = 0; i < m; i++ ){ 32 int u, v; 33 scanf( "%d%d", &u, &v ); 34 vis[u]++; 35 vet[v].push_back( u ); 36 } 37 priority_queue<int> que; 38 for( int i = 1; i <= n; i++ ){ 39 if( !vis[i] ) que.push( i ); 40 } 41 while( !que.empty() ){ 42 int u = que.top(); que.pop(); 43 for( int i = 0; i < vet[u].size(); i++ ){ 44 vis[vet[u][i]]--; 45 if( vis[vet[u][i]] == 0 ){ 46 que.push( vet[u][i] ); 47 } 48 } 49 ans[cnt++] = u; 50 } 51 for( int i = cnt-1; i >= 0; i-- ){ 52 if( i == 0 ){ 53 cout<<ans[i]<<endl; 54 } 55 else cout<<ans[i]<<" "; 56 } 57 } 58 return 0; 59 } 60 /*给出几组数据大家试一下 61 10 62 3 1 63 3 1 64 answer : 3 1 2 65 3 1 66 1 3 67 answer : 1 2 3 68 4 3 69 3 1 70 4 1 71 2 4 72 answer : 2 3 1 4 73 9 12 74 1 2 75 2 8 76 2 9 77 2 4 78 4 3 79 4 5 80 4 7 81 9 3 82 9 6 83 9 5 84 8 5 85 8 7 86 answer : 1 2 4 9 3 8 5 6 7 87 按照字典序最小输出 88 int vv[mnx], first[mnx], nxt[mnx], e, d[mnx], ans[mnx], n; 89 void add( int u, int v ){ 90 vv[e] = v, nxt[e] = first[u], first[u] = e++; 91 } 92 int main(){ 93 n = 8; 94 memset( d, 0, sizeof(d) ); 95 memset( first, -1, sizeof(first) ); 96 for( int i = 0; i < 6; i++ ){ 97 int u, v; 98 scanf( "%d%d", &u, &v ); 99 add( u, v );100 d[v]++;101 }102 int cnt = 0;103 priority_queue< int, vector<int>, greater<int> > q;104 for( int i = 1; i <= n; i++ ){105 if( d[i] == 0 ) q.push( i );106 }107 while( !q.empty() ){108 int u = q.top(); q.pop();109 ans[cnt++] = u;110 for( int i = first[u]; i != -1; i = nxt[i] ){111 int v = vv[i];112 d[v]--;113 if( d[v] == 0 ) q.push( v );114 }115 for( int i = 0; i < n; i++ ){116 cout<<ans[i]<<" ";117 }118 cout<<endl;119 }120 return 0;121 }122 123 */
hdu 4858 项目管理
第二题数据比较水，暴力可以就过了。。赛后问了超哥正解，好像是图的分块：按点的度数和sqrtn分块，度数大于sqrtn的点最多有sqrtn个，把大点和大点建图，更新首先直接更新自己的值，然后更新小点的时候，一并更新小点连接的所有大点的答案，更新大点的时候，把相邻的大点也更新答案，询问的话，小点直接for循环累加val值，大点直接返回答案。。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std;11 12 #define mnx 10400013 #define ll long long14 #define inf 0x3f3f3f3f15 #define lson l, m, rt << 116 #define rson m+1, r, rt << 1 | 117 18 vector<int> g1[mnx], g2[mnx];19 int d[mnx], val[mnx], ans[mnx], n, m;;20 void init(){21 for( int i = 1; i <= n; i++ ){22 if( d[i] > 333 )23 for( int j = 0; j < g1[i].size(); j++ )24 if( d[g1[i][j]] > 333 ) 25 g2[i].push_back( g1[i][j] );26 }27 }28 void upd(){29 int u, v;30 scanf( "%d%d", &u, &v );31 val[u] += v;32 if( ans[u] <= 333 ){33 for( int i = 0; i < g1[u].size(); i++ ){34 int V = g1[u][i];35 if( d[V] > 333 ) ans[V] += v;36 }37 }38 else for( int i = 0; i < g2[u].size(); i++ ){39 ans[ g2[u][i] ] += v;40 }41 }42 void cal(){43 int u;44 scanf( "%d", &u );45 if( d[u] > 333 ) printf( "%d\n", ans[u] );46 else{47 int sol = 0;48 for( int i = 0; i < g1[u].size(); i++ ){49 sol += val[ g1[u][i] ];50 }51 printf( "%d\n", sol );52 }53 }54 int main(){55 int cas;56 scanf( "%d", &cas );57 while( cas-- ){58 for( int i = 0; i < mnx; i++ ){59 g1[i].clear(), g2[i].clear();60 }61 memset( ans, 0, sizeof(ans) );62 memset( d, 0, sizeof(d) );63 memset( val, 0, sizeof(val) );64 scanf( "%d%d", &n, &m );65 for( int i = 0; i < m; i++ ){66 int u, v;67 scanf( "%d%d", &u, &v );68 g1[u].push_back( v ), g1[v].push_back( u );69 d[u]++, d[v]++;70 }71 init();72 int q;73 scanf( "%d", &q );74 while( q-- ){75 int cmd;76 scanf( "%d", &cmd );77 if( cmd == 0 ){78 upd();79 }80 else cal();81 }82 }83 return 0;84 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。