E - Andrew and Taxi-二分答案-topo判环

E - Andrew and Taxi

思路 :min max   明显二分答案,二分需要破坏的那些边的中机器人数量最多的那个。

check 过程建边时直接忽略掉小于 mid 的边,这样去检验有无环存在即可。 当时有一点担心会出现

有一个环 有一条边 反过来之后 这个环破坏了 却成就了 另一个环,但是画图发现 这样的图 ,它们两边会形成

一个大环。那个大环一定会通过别的边破坏掉,所以不需要担心这种情况。topo 判环即可。

#include<bits/stdc++.h>
using namespace std;
#define maxn 1234567
int n,m,head[maxn],ord[maxn],id;
int cnt,u,v,w,in[maxn],l,r,s;
vector<int>p;
struct data
{
int u,v,w;
} e[maxn];
struct node
{
int to,v,w;
} edge[maxn];
void add(int u,int v,int w)
{
edge[++cnt].v=v;
edge[cnt].to=head[u];
edge[cnt].w=w;
head[u]=cnt;
in[v]++;
}
void topo(int x)
{
id=cnt=0;
queue<int>q;
while(!q.empty())q.pop();
for(int i=0; i<=n; i++)
{
head[i]=-1;
ord[i]=in[i]=0;
}
for(int i=0; i<m; i++)
if(e[i].w>x)add(e[i].u,e[i].v,e[i].w);
for(int i=1; i<=n; i++)
{
if(in[i]==0)
{
q.push(i);
ord[i]=++id;
}
}
while(!q.empty())
{
u=q.front();
q.pop();
for(int i=head[u]; i!=-1; i=edge[i].to)
{
v=edge[i].v;
in[v]--;
if(in[v]==0)
{
q.push(v);
ord[v]=++id;
}
}
}
}
bool ok(int x)
{
topo(x);
if(id<n)return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0; i<m; i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
r=1e9;
while(l<=r)
{
int mid=(l+r)/2;
if(ok(mid))r=mid-1;
else l=mid+1;
}
topo(l);
for(int i=0; i<m; i++)
if(ord[e[i].u]>ord[e[i].v])
p.push_back(i+1);
s=p.size();
printf("%d %d \n",l,s);
for(int i=0; i<s; i++)
{
printf("%d",p[i]);
if(i<s)printf(" ");
else printf("\n");
}
return 0;
}

  

上一篇:APK改之理 手游修改改编安卓程序工具安装使用教程


下一篇:Win 2008 R2安装SQL Server 2008“性能计数器注册表配置单元一致性”失败的解决办法