HZOJ 那一天她离我而去

一个数据水到不行的题，各路大佬用各种方法A掉了这个题（比如A*，最短路，dfs……）。

这里只说一下我的暴力和被碾压的正解。

暴力AC系列：

要找过1点的最小环，那么这个环可以拆成两部分，与1相连的两点经过1的距离和不过一的最短路，那么我们就可以将1的入边截断（出边当然也可以截断，这里是为了方便枚举）并记录这些点到1的距离，枚举与1相连的点，对于每个点跑最短路，再次枚举每个点，ans取min即可。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 #define LL long long

 #define MAXN 10010

 #define min(a,b) ((a)<(b)?(a):(b))

 #define ma(x) memset(x,0,sizeof(x))

 #define MP(a,b) make_pair(a,b)

 using namespace std;

 struct edge

 {

     int u,v,w,nxt;

     #define u(x) ed[x].u

     #define v(x) ed[x].v

     #define w(x) ed[x].w

     #define n(x) ed[x].nxt

 }ed[MAXN*];

 int first[MAXN],num_e;

 #define f(x) first[x]

 int T,n,m;

 const int t=;

 int dis[MAXN];

 bool v[MAXN];

 void dist(int st)

 {

     memset(dis,0x7f,sizeof(dis));ma(v);

     dis[st]=;

     priority_queue<pair<int,int> >q;

     q.push(MP(,st));

     while(!q.empty())

     {

         int k=q.top().second;q.pop();

         if(v[k])continue;v[k]=;

         for(int i=f(k);i;i=n(i))

         if(dis[v(i)]>dis[k]+w(i))

             dis[v(i)]=dis[k]+w(i),

             q.push(MP(-dis[v(i)],v(i)));

     }

 }

 int tem[MAXN];

 inline void add(int u,int v,int w);

 signed main()

 {

     cin>>T;

     while(T--)

     {

         memset(tem,0x7f,sizeof(tem));

         ma(first);num_e=;

         cin>>n>>m;

         int u,v,d;

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

         {

             cin>>u>>v>>d;

             if(u!=)add(v,u,d);

             if(v!=)add(u,v,d);

             if(u==)tem[v]=d;

             if(v==)tem[u]=d;

         }

         LL ans=0x7fffff;

         for(int i=f();i;i=n(i))

         {

             dist(v(i));

             for(int j=f();j;j=n(j))

             if(v(i)!=v(j))

                 ans=min(ans,dis[v(j)]+tem[v(j)]+tem[v(i)]);

         }

         printf("%lld\n",ans==0x7fffff?-:ans);

     }

 }

 inline void add(int u,int v,int w)

 {

     ++num_e;

     u(num_e)=u;

     v(num_e)=v;

     w(num_e)=w;

     n(num_e)=f(u);

     f(u)=num_e;

 }

正解：

这题如果数据做的厉害一点肯定也是一个巨坑的题，正解大概和上边的暴力思路相似，只是优化了一点，将与1相连的点分组（分组方法一会再说），一组作为起点，建立超级源点向这一组每个点连边权为0的边，建立超级汇点，从另外一组每个点向超级汇点连边权为0的边，跑最短路即可。如果我们可以保证最终答案的起点与终点分到了两组，求出的就是正确答案。

接下来说nb的分组方法：

将每个节点按照编号转化为二进制数，从第0位开始，编号为0的分一组，编号为1的分另一组，这样也就跑了十边最短路的样子。

但这样能确保最后答案的起点和终点分到两个组吗？显然可以，因为起点和终点的编号不同，二进制为至少有一位不同，也就至少有一次被分到不同组。

然而正解的代码好像并没有人打……

巴特西

HZOJ 那一天她离我而去

最新文章

热门文章