2015 ACM Arabella Collegiate Programming Contest

　　题目链接：https://vjudge.net/contest/154238#overview。

　　ABCDE都是水题。

　　F题，一开始分类讨论，结果似乎写挫了，WA了一发。果断换并查集上，A了。

　　G题，状态压缩DP，不难写，但是时限有点紧，读入也比较恶心。。值得注意的是计算一个数二进制下有几个1可以用__builtin_popcount(mask)；判断a和b在二进制表示下a是不是b的子集可以用(a&b)==a；另外字符串s想移除最后一位可以s.resize(s.size()-1)或者s.erase(s.end()-1)。

　　H题，tarjan题，思路不难。无向图缩点以后找一下树的直径，再遍历一下即可。但是被两个傻逼错误卡了好久。。好弱啊。。顺便注意下，无向图的缩点需要在tarjan的时候加一个参数fa，或者用head数组实现邻接表。后者因为反向边和原边的编号是相邻的，可以直接用vis数组来使得反向边不访问，这个方法的好处是可以处理重边，而第一个方法不行。具体的代码实现我之前的模板里有。。贴一下这题的代码好了：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <iostream>

 #include <stdlib.h>

 #include <string>

 #include <stack>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 typedef long long ll;

 typedef pair<int,int> pii;

 const int N =  + ;

 int n,m,dfs_clock,dfn[N],low[N];

 int belong[N],scc_cnt,id[N];

 stack<int> S;

 struct edge

 {

     int v,w,nxt;

 }G[N*];

 int head[N],head2[N],etot;

 vector<int> bcc[N];

 void addEdge(int u,int v,int w,int* head)

 {

     G[etot] = (edge){v,w,head[u]};

     head[u] = etot++;

 }

 int pos = ;

 void init()

 {

     etot = ;

     memset(head,-,sizeof head);

     memset(head2,-,sizeof head2);

     dfs_clock = ;

     memset(dfn,,sizeof(dfn));

     memset(belong,,sizeof(belong));

     scc_cnt = ;

     memset(id,-,sizeof(id));

 }

 void tarjan(int u,int fa)

 {

     dfn[u]=low[u]=++dfs_clock;

     S.push(u);

     for(int i=head[u];i!=-;i=G[i].nxt)

     {

         edge e = G[i];

         int v = e.v;

         if(!dfn[v])

         {

             tarjan(v,u);

             low[u]=min(low[u],low[v]);

         }

         else if(dfn[v] < dfn[u] && v != fa)

         {

             low[u]=min(low[u],dfn[v]);

         }

     }

     if(low[u]==dfn[u])

     {

         scc_cnt++;

         bcc[scc_cnt].clear();

         for(;;)

         {

             int x = S.top();S.pop();

             belong[x] = scc_cnt;

             bcc[scc_cnt].push_back(x);

             if(id[scc_cnt] == - || id[scc_cnt] > x) id[scc_cnt] = x;

             if(x==u) break;

         }

     }

 }

 ll d[N],d1[N],d2[N];

 void dfs(int u,int fa,ll* dis)

 {

     for(int i=head2[u];i!=-;i=G[i].nxt)

     {

         edge e = G[i];

         int v = e.v, w = e.w;

         if(v == fa) continue;

         dis[v] = dis[u] + w;

         dfs(v,u,dis);

     }

 }

 void solve()

 {

     for(int i=;i<=n;i++)

     {

         if(!dfn[i]) tarjan(i,-);

     }

     for(int i=;i<=n;i++)

     {

         int u = belong[i];

         for(int j=head[i];j!=-;j=G[j].nxt)

         {

             edge e = G[j];

             int v = belong[e.v], w = e.w;

             if(u != v)

             {

                 addEdge(u,v,w,head2);

             }

         }

     }

     int x = belong[];

     d[x] = ;

     dfs(x,-,d);

     int y = x;

     for(int i=;i<=scc_cnt;i++)

     {

         if(d[i] > d[y])

         {

             y = i;

         }

     }

     d1[y] = ;

     dfs(y,-,d1);

     x = y;

     for(int i=;i<=scc_cnt;i++)

     {

         if(d1[i] > d1[x])

         {

             x = i;

         }

     }

     d2[x] = ;

     dfs(x,-,d2);

     int ans_id = min(id[x],id[y]);

     ll len = d1[belong[ans_id]] + d2[belong[ans_id]];

     for(int i=;i<=scc_cnt;i++)

     {

         ll temp = max(d1[i], d2[i]);

         if(temp < len)

         {

             ans_id = id[i];

             len = temp;

         }

         else if(temp == len && id[i] < ans_id) ans_id = id[i];

     }

     printf("%d %I64d\n",ans_id,len);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     for(int kase=;kase<=T;kase++)

     {

         init();

         scanf("%d%d",&n,&m);

         for(int i=;i<=m;i++)

         {

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

             addEdge(u,v,w,head);

             addEdge(v,u,w,head);

         }

         solve();

     }

 }

H题

巴特西

2015 ACM Arabella Collegiate Programming Contest

最新文章

热门文章