2025年2020NYIST个人积分赛第一场（二分+拓扑排序）

科技前沿 • 2025-02-25 09:08 • 阅读 30

大家好，我是讯享网，很高兴认识大家。

题意：

一个n个节点的有向图，节点标号从1到n，存在m条单向边。每条单向边有一个权值，代表翻转其方向所需的代价。求使图变成无环图，其中翻转的最大边权值最小的方案，以及该方案翻转的最大的边权。

输入：

输出：

在第一行中输出两个整数，即要翻转的最大的边权，和需要反转道路数量k。k不需要是最小的。
在下一行输出k个由空格分隔的整数，表示需要翻转的道路编号
如果有许多解决方案，请打印其中任何一个

讯享网

样例：

Input
5 6
2 1 1
5 2 6
2 3 2
3 4 3
4 5 5
1 5 4
Output
2 2
1 3
Input
5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3
Output
3 3
3 4 7

思路：

由于图是有向图，并且题目符合二分特性，我们可以用拓扑排序+加二分解决，我们通过二分，枚举边权，将大于mid的边的入度++,然后进行一波拓扑排序，如果拓扑成功，则说明当前的mid可以，所以我们就缩小mid，如果失败则说明当前的mid不行，我们需要扩大mid，因为小于mid的我们可以进行任意的修改，所以，我们就通过这种方式进行不断缩进，得到最小边权中的最大，并在过程中不段更新形成环的边即可

注意：l需要从0开始，因为可能图符合拓扑排序没有最大边权

参考代码：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+5; struct node { 
    int to,nex,w,id; }edge[maxn]; int head[maxn],cnt; void add(int u,int v,int w,int id) { 
    edge[cnt]=node{ 
   v,head[u],w,id}; head[u]=cnt++; } int n,m,k; int topo[maxn],in[maxn],e[maxn]; bool check(int mid) { 
    queue<int>q; memset(in,0,sizeof(in)); memset(topo,0,sizeof(topo)); for(int i=1;i<=n;i++) { 
    for(int j=head[i];~j;j=edge[j].nex) { 
    if(edge[j].w<=mid) continue; in[edge[j].to]++; } } for(int i=1;i<=n;i++) if(!in[i]) q.push(i); int cnx=0; while(!q.empty()) { 
    int u=q.front(); topo[u]=++cnx; q.pop(); for(int i=head[u];~i;i=edge[i].nex) { 
    if(edge[i].w<=mid) continue; int v=edge[i].to; in[v]--; if(!in[v]) q.push(v); } } if(cnx!=n) return false; k=0; for(int i=1;i<=n;i++) { 
    for(int j=head[i];~j;j=edge[j].nex) { 
    if(edge[j].w>mid) continue; //根据拓扑序,判断形成环的边加入e{ } if(topo[i]>topo[edge[j].to]) e[k++]=edge[j].id; } } return true; } int main() { 
    ios::sync_with_stdio(false); cin.tie(0); memset(head,-1,sizeof head); cin>>n>>m; int u,v,w; int l=0,r=0; for(int i=1;i<=m;i++) cin>>u>>v>>w,add(u,v,w,i),r=max(r,w); int ans=0; while(l<=r) { 
    int mid=l+r>>1; if(check(mid)) { 
    r=mid-1; ans=mid; } else { 
    l=mid+1; } } sort(e,e+k); cout<<ans<<' '<<k<<endl; for(int i=0;i<k;i++) cout<<e[i]<<' '; cout<<endl; }

讯享网

2025年2020NYIST个人积分赛第一场 （二分+拓扑排序）

相关推荐

2025年2020NYIST个人积分赛第一场（二分+拓扑排序）