傳送門：QAQQAQ

?

題意：給你一個圖，每條邊有邊權，現在你可以對邊進行反轉，使圖中不存在環，你需要使得反轉的邊的邊權集合中的最大值最小，并輸出任意一組解。

?

思路：二分+拓撲排序

使得最大值最小，自然而然想到二分（其實我先想到tarjan，發現環套環無法處理）

那么我們二分枚舉答案，把小于mid的邊全部拆了，判斷剩下邊是否成環（dfs，之前染色方法玄學錯誤），若沒有環則當前mid成立

為什么呢？——如果我們把一條刪掉的邊連上，無論怎么擺都會形成一個環，那么原先的邊一定有一條大環，所以原先這種情況就不可能成立（畫個圖可以模擬一下）

?

那么現在我們已經證明刪掉的邊按照一定順序擺一定不會有環，我們只需要找出一種這樣的順序。

進行拓撲排序，如果一條邊是由拓撲序大的連向拓撲序小的，我們就將它反轉，這樣就可以保證沒有壞

證明：刪掉比mid小的邊后剩下的一定是若干個DAG，產生環的根本原因是兒子有返祖邊，而父親拓撲序一定比兒子小（因為是用queue維護的），所以若所有邊都從拓撲序小的連向拓撲序大的，就一定不會產生返祖邊

?

代碼：

#include<bits/stdc++.h> using namespace std; const int N=210000;struct node{int from,to,cost,id; }E[N]; vector<int> v;int first[N],nxt[N],point[N],w[N],e=0,dfn[N]; void add_edge(int x,int y,int z,int num) {e++;E[num].id=e;point[e]=y; w[e]=z;nxt[e]=first[x];first[x]=e; }bool cmp(node x,node y) {if(x.cost==y.cost) return x.id<y.id;return x.cost<y.cost; }int vis[N],bl[N],n,m,judge,best,in[N]; void dfs(int u) {vis[u]=2;for(int i=first[u];i!=-1;i=nxt[i]){if(bl[i]) continue;int p=point[i];if(vis[p]==2) {judge=0;return;}if(!vis[p]) dfs(p); }vis[u]=1;return; }bool check(int mid) {judge=1; memset(vis,0,sizeof(vis));memset(bl,0,sizeof(bl));for(int i=1;i<=mid;i++) bl[E[i].id]=1; for(int i=1;i<=n;i++) {if(!vis[i]) {dfs(i);}}return judge; }int main() {memset(first,-1,sizeof(first));memset(nxt,-1,sizeof(nxt));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&E[i].from,&E[i].to,&E[i].cost);add_edge(E[i].from,E[i].to,E[i].cost,i);}sort(E+1,E+m+1,cmp);int l=0,r=m,mid;best=-1;while(l<=r){mid=(l+r)>>1;if(check(mid)) r=mid-1,best=mid;else l=mid+1;}queue<int> q;int tot=0;memset(in,0,sizeof(in));for(int i=best+1;i<=m;i++){in[E[i].to]++;}for(int i=1;i<=n;i++) if(!in[i]) q.push(i);memset(bl,0,sizeof(bl));for(int i=1;i<=best;i++) bl[E[i].id]=1;while(!q.empty()){int now=q.front();q.pop();dfn[now]=++tot;for(int i=first[now];i!=-1;i=nxt[i]){if(bl[i]) continue;int pos=point[i];in[pos]--;if(!in[pos]) q.push(pos); }}for(int i=1;i<=best;i++) {int x=E[i].from;int y=E[i].to;if(dfn[x]>dfn[y]) v.push_back(E[i].id);}printf("%d %d\n",E[best].cost,(int)v.size());for(int i=0;i<(int)v.size();i++) printf("%d ",v[i]);return 0; } View Code

?

轉載于:https://www.cnblogs.com/Forever-666/p/11235050.html

總結

以上是生活随笔為你收集整理的codeforces 1100E-Andrew and Taxi的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。