E. Andrew and Taxi（二分+拓扑判环）

65 阅读 0 评论 43 点赞

我是靠谱客的博主无聊茉莉，最近开发中收集的这篇文章主要介绍E. Andrew and Taxi（二分+拓扑判环），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：http://codeforces.com/contest/1100/problem/E

题目大意：给你n和m，n代表有n个城市，m代表有m条边，然后m行输入三个数，起点，终点，花费。，每一条边的花费指的是将这条路方向反转的花费。然后问你使得整个图没有环的最小花费。（这里的最小花费指的是改变方向的边中，权值最大的那个）。

具体思路：二分答案，我们找出符合题目条件的最优解，check的时候，建立边权大于当前值的边，我们是通过形成的图判断有没有环来检验的，找到最优解之后，将剩余边权的大于最优解的边建立一个图，然后进行拓扑排序。再枚举每一条边，看这一条边的起点和终点的拓扑序，如果说起点的拓扑序大于终点的拓扑序，也就是说这条边应该是方向翻转，然后找出这满足情况的边就可以了。

反思：

1.这样为什么可以呢？昨晚打比赛的时候想到了一种情况，就是如果将当前的一条边翻转之后，原来的图中的环会不再存在，但是会形成新的图，这样的话也是不行的，但是对于这种情况，画画图就知道了，这种情况的话，外面肯定是有一个大环的，我们只需要对这个大环进行操作就可以了（操作的边数没有限制，只要这条边权比当前二分的值小就可以了）。

AC代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <cstring>
  6 #include <ctime>
  7 #include <algorithm>
  8 #include <map>
  9 #include <vector>
 10 #include <queue>
 11 using namespace std;
 12 # define ll long long
 13 # define pi acos(-1.0)
 14 const int maxn  = 1e5+100;
 15 int deg[maxn],head[maxn],ord[maxn],vis[maxn];
 16 int num,n,m;
 17 vector<int>qq;
 18 struct node
 19 {
 20     int fr;
 21     int to;
 22     int nex;
 23     int cost;
 24 } q[maxn],edge[maxn*2];
 25 void init()
 26 {
 27     num=0;
 28     memset(head,-1,sizeof(head));
 29     memset(deg,0,sizeof(deg));
 30 }
 31 void addedge(int fr,int to)
 32 {
 33     edge[num].to=to;
 34     edge[num].nex=head[fr];
 35     head[fr]=num++;
 36     deg[to]++;
 37 }
 38 bool check(int t)
 39 {
 40     memset(vis,0,sizeof(vis));
 41     init();
 42     for(int i=1; i<=m; i++)
 43     {
 44         if(q[i].cost>t)
 45             addedge(q[i].fr,q[i].to);
 46     }
 47     queue<int>wakaka;
 48     for(int i=1;i<=n;i++){
 49     if(deg[i]==0){
 50     wakaka.push(i);
 51     }
 52     }
 53     while(!wakaka.empty()){
 54     int top=wakaka.front();
 55     wakaka.pop();
 56     vis[top]=1;
 57     for(int i=head[top];i!=-1;i=edge[i].nex){
 58     int u=edge[i].to;
 59     if(--deg[u]==0)wakaka.push(u);
 60     }
 61     }
 62     for(int i=1;i<=n;i++){
 63     if(vis[i]==0)return false;//(拓扑判环)
 64     }
 65     return true;
 66 }
 67 int main()
 68 {
 69     scanf("%d %d",&n,&m);
 70     for(int i=1; i<=m; i++)
 71     {
 72         scanf("%d %d %d",&q[i].fr,&q[i].to,&q[i].cost);
 73     }
 74     int l=0,r=1e9;
 75     while(l<r)
 76     {
 77         int mid=(l+r)/2;
 78         if(check(mid))
 79         {
 80             r=mid;
 81         }
 82         else
 83             l=mid+1;
 84     }
 85     init();
 86     for(int i=1; i<=m; i++)
 87     {
 88         if(q[i].cost>r)
 89         {
 90             addedge(q[i].fr,q[i].to);
 91         }
 92     }
 93     queue<int>wakaka;
 94     for(int i=1; i<=n; i++)
 95     {
 96         if(!deg[i])
 97             wakaka.push(i);
 98     }
 99     memset(ord,0,sizeof(ord));
100     int ans=0;
101     while(!wakaka.empty())
102     {
103         int top=wakaka.front();
104         wakaka.pop();
105         ord[top]=++ans;
106         for(int i=head[top]; i!=-1; i=edge[i].nex)
107         {
108             int to=edge[i].to;
109             deg[to]--;
110             if(!deg[to])
111             {
112                 wakaka.push(to);
113             }
114         }
115     }
116     for(int i=1; i<=m; i++)
117     {
118         if(ord[q[i].fr]>ord[q[i].to])//（拓扑序）
119         {
120             qq.push_back(i);
121         }
122     }
123     printf("%d %dn",r,qq.size());
124     int len=qq.size();
125     for(int i=0; i<len; i++)
126     {
127         if(i==0)
128             printf("%d",qq[i]);
129         else
130             printf(" %d",qq[i]);
131     }
132     printf("n");
133     return 0;
134 }