最小生成樹，兩節點編號都＞k的直接連邊，否則累計不滿足這種情況的邊的數量len，對這些邊建生成樹，這len條邊中不在生成樹上的邊就是最少要刪去的邊 （證明的話因為如果成環了那無論刪那條邊都是一樣的吧..我是這樣理解的）
code：
#include<map>#include<set>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long longusing namespace std;void read(int &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}void up(int &x,int y){if(x<y)x=y;}const int maxn = 1100000;const int maxm = 2100000;int fa[maxn],n,m,k;int find_(int x){ if(fa[x]==x) return x; return fa[x]=find_(fa[x]);}int d[maxm][2],len;int main(){ read(n); read(m); read(k); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { int x,y; read(x); read(y); if(x>k&&y>k) fa[find_(x)]=find_(y); else len++,d[len][0]=x,d[len][1]=y; } int s=0; for(int i=1;i<=len;i++) { int x=d[i][0],y=d[i][1]; int f1=find_(x), f2=find_(y); if(f1!=f2) fa[f1]=f2,s++; }新聞熱點
疑難解答
