HDU 1599 find the mincost route （无向图的最小环）

题意：

　　给一个带权无向图，求其至少有3个点组成的环的最小权之和。

思路：

　　（1）DFS可以做，实现了确实可以，只是TLE了。量少的时候应该还是可以水一下的。主要思路就是，深搜过程如果当前点搜到一个点访问过了，而其不是当前点的父亲，则肯定有环，可以更新答案。深搜过程要记录路径和，父亲，是否访问过等等信息，因为图可能有多个连通分量。

 #include <bits/stdc++.h>

 #define INF 0x7f7f7f7f

 #define pii pair<int,int>

 #define LL unsigned long long

 using namespace std;

 const int N=;

 struct node

 {

     int from, to, cost;

     node(){};

     node(int from,int to,int cost):from(from),to(to),cost(cost){};

 }edge[N*N];

 int edge_cnt;

 vector<int> vect[N];

 void add_node(int from,int to,int cost)

 {

     edge[edge_cnt]=node(from, to, cost);

     vect[from].push_back(edge_cnt++);

 }

 int sum[N], vis[N], inq[N], pre[N], ans;

 void DFS(int x)

 {

     vis[x]=;

     inq[x]=;

     for(int i=; i<vect[x].size(); i++)

     {

         node e=edge[vect[x][i]];

         if( inq[e.to] && pre[x]!=e.to )

         {

             ans=min(ans, sum[x]+e.cost-sum[e.to]);

         }

         if( !inq[e.to] )

         {

             pre[e.to]=x;

             sum[e.to]=sum[x]+e.cost;

             DFS(e.to);

             sum[e.to]=;

             pre[e.to]=;

         }

     }

     inq[x]=;

 }

 int cal(int n)

 {

     ans=INF;

     memset(vis,,sizeof(vis));

     memset(inq,,sizeof(inq));

     memset(pre,,sizeof(pre));

     memset(sum,,sizeof(sum));

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

     {

         if(!vis[i])

             DFS(i);

     }

     return ans==INF? : ans;

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int t, a, b, c, n, m;

     while(~scanf("%d %d", &n, &m))

     {

         edge_cnt=;

         for(int i=; i<=n; i++) vect[i].clear();

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

         {

             scanf("%d%d%d",&a,&b,&c);

             add_node(a, b, c);

             add_node(b, a, c);

         }

         int ans=cal(n);

         if(ans) printf("%d\n", ans);

         else    printf("It's impossible.\n");

     }

     return ;

 }

TLE代码

　　（2）dijkstra。枚举删除某一条边，求该边两点间的最短距离。要注意的是，重边只留1条权最小的，其他删掉，这样就能保证至少出现3个点。

　　608ms

 #include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 #include <deque>

 #define INF 0x7f7f7f7f

 #define pii pair<int,int>

 #define LL unsigned long long

 using namespace std;

 const int N=;

 struct node

 {

     int from, to, cost, tag;

     node(){};

     node(int from,int to,int cost):from(from),to(to),cost(cost),tag(){};

 }edge[N*N];

 int edge_cnt;

 vector<int> vect[N];

 int g[N][N];

 void add_node(int from,int to,int cost)

 {

     edge[edge_cnt]=node(from, to, cost);

     vect[from].push_back(edge_cnt++);

 }

 int vis[N], cost[N];

 int dijkstra(int s,int e)

 {

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

     memset(vis, , sizeof(vis));

     cost[s]=;

     priority_queue<pii,vector<pii>,greater<pii> > que;

     que.push(make_pair(, s));

     while(!que.empty())

     {

         int x=que.top().second;

         que.pop();

         if(vis[x])  continue;

         vis[x]=;

         for(int i=; i<vect[x].size(); i++)

         {

             node e=edge[vect[x][i]];

             if( e.tag && cost[e.to]>cost[x]+e.cost )

             {

                 cost[e.to]=cost[x]+e.cost;

                 que.push(make_pair(cost[e.to], e.to));

             }

         }

     }

     return cost[e];

 }

 int cal()

 {

     int ans=INF;

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

     {

         edge[i].tag=;

         edge[i^].tag=;

         ans=min(ans, edge[i].cost+dijkstra(edge[i].from, edge[i].to));

         edge[i].tag=;

         edge[i^].tag=;

     }

     return ans==INF? : ans;

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int t, a, b, c, n, m;

     while(~scanf("%d %d", &n, &m))

     {

         edge_cnt=;

         for(int i=; i<=n; i++) vect[i].clear();

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

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

         {

             scanf("%d%d%d",&a,&b,&c);

             g[b][a]=g[a][b]=min(g[a][b], c);

         }

         for(int i=; i<=n; i++) //为了去重边

         {

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

             {

                 if(g[i][j]<INF)

                 {

                     add_node(i, j, g[i][j]);

                     add_node(j, i, g[i][j]);

                 }

             }

         }

         int ans=cal();

         if(ans) printf("%d\n", ans);

         else    printf("It's impossible.\n");

     }

     return ;

 }

AC代码

　　（3）floyd。dijkstra是枚举删某条边，而floyd是枚举相连的两条边。先理解floyd的思想，穷举每个点k作为中间节点来更新其他点a和b之间的距离，而当某个点未被k枚举到时，是不可能有一条路径将其包含在中间的，它顶多可以作为路径的起点或者终点。利用这点，在未枚举到某点k作为中间点时，可以枚举一下与k相连的两条边，即i->k->j。

　　78ms

 #include <bits/stdc++.h>

 #define INF 0x7f7f7f7f

 #define pii pair<int,int>

 #define LL unsigned long long

 using namespace std;

 const int N=;

 int g[N][N], dist[N][N];

 int cal(int n)  //floyd

 {

     int ans=INF;

     for(int k=; k<=n; k++) //注意枚举顺序。

     {

         //枚举两条边i->k->j。

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

         {

             if(g[i][k]==INF || k==i) continue;

             for(int j=i+; j<=n; j++)   //i和j不能相等，才能保证至少3个点。

             {

                 if(g[k][j]==INF || dist[i][j]==INF || k==j )    continue;

                 int dis=g[i][k] + g[k][j] + dist[i][j];

                 ans=min(ans, dis);

             }

         }

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

         {

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

             {

                 if(dist[i][k]==INF || dist[k][j]==INF) continue;

                 dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);

             }

         }

     }

     return ans==INF? : ans;

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int t, a, b, c, n, m;

     while(~scanf("%d %d", &n, &m))

     {

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

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

         {

             scanf("%d%d%d",&a,&b,&c);

             g[b][a]=g[a][b]=min(g[a][b], c);

         }

         memcpy(dist, g, sizeof(g));

         for(int i=; i<=n; i++) dist[i][i]=;

         int ans=cal(n);

         if(ans) printf("%d\n", ans);

         else    printf("It's impossible.\n");

     }

     return ;

 }

AC代码

巴特西

HDU 1599 find the mincost route （无向图的最小环）

最新文章

热门文章