网络流+最小生成树的最少割边数--How Many to Be Happy? _生成树

农村四月闲人少，勤学苦攻把名扬。这篇文章主要讲述网络流+最小生成树的最少割边数--How Many to Be Happy?相关的知识，希望能为你提供帮助。
题意：https://blog.csdn.net/Ratina/article/details/95200594
思路：
首先我们知道最小生成树就是按长度枚举边，能连就连。
那么，如果这条边在最小生成树里，那我们只需要看比它短的边是不是已经使当前的u---v连通，如果连通最少需要切掉几条（边权为1跑最小割）。
所以我们对边排序，枚举边+重构图跑Dinic就行了。

1 #define ios ios_base::sync_with_stdio(0); cin.tie(0); 2 #include < cstdio> //sprintf islower isupper 3 #include < cstdlib> //mallocexit strcat itoa system("cls") 4 #include < iostream> //pair 5 #include < fstream> //freopen("C:\Users\13606\Desktop\Input.txt","r",stdin); 6 #include < bitset> 7 //#include < map> 8 //#include< unordered_map> 9 #include < vector> 10 #include < stack> 11 #include < set> 12 #include < string.h> //strstr substr 13 #include < string> 14 #include < time.h> // srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9; 15 #include < cmath> 16 #include < deque> 17 #include < queue> //priority_queue< int, vector< int> , greater< int> > q; //less 18 #include < vector> //emplace_back 19 //#include < math.h> 20 #include < cassert> 21 //#include < windows.h> //reverse(a,a+len); // ~ ! ~ ! floor 22 #include < algorithm> //sort + unique : sz=unique(b+1,b+n+1)-(b+1); +nth_element(first, nth, last, compare) 23 using namespace std; //next_permutation(a+1,a+1+n); //prev_permutation 24 //****************** 25 int abss(int a); 26 int lowbit(int n); 27 int Del_bit_1(int n); 28 int maxx(int a,int b); 29 int minn(int a,int b); 30 double fabss(double a); 31 void swapp(int & a,int & b); 32 clock_t __STRAT,__END; 33 double __TOTALTIME; 34 void _MS(){__STRAT=clock(); } 35 void _ME(){__END=clock(); __TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC; cout< < "Time: "< < __TOTALTIME< < " s"< < endl; } 36 //*********************** 37 #define rint register int 38 #define fo(a,b,c) for(rint a=b; a< =c; ++a) 39 #define fr(a,b,c) for(rint a=b; a> =c; --a) 40 #define mem(a,b) memset(a,b,sizeof(a)) 41 #define pr printf 42 #define sc scanf 43 #define ls rt< < 1 44 #define rs rt< < 1|1 45 typedef vector< int> VI; 46 typedef long long ll; 47 const double E=2.718281828; 48 const double PI=acos(-1.0); 49 //const ll INF=(1LL< < 60); 50 const int inf=(1< < 30); 51 const double ESP=1e-9; 52 const int mod=(int)1e9+7; 53 const int N=(int)1e3+10; 54 const int M=(int)5e3+5; 55 56 class DINIC 57 { 58 public: 59 //const int MAXN=10004,MAXWAY=100005; 60int n,way,max_flow,deep[N]; 61int tot,head[N],cur[N]; 62struct EDGE{ 63int to,next; 64int dis; 65}edge[M]; 66void Init(int n_) 67{ 68tot=-1; //因为加反向边要^1,所以要从0开始; 69n=n_; 70max_flow=0; 71for(int i=0; i< =n_; ++i) 72head[i]=-1; 73} 74void add(int from,int to,int V) 75{ 76//正向 77++tot; 78edge[tot].to=to; 79edge[tot].dis=V; 80edge[tot].next=head[from]; 81head[from]=tot; 82//反向 83swap(from,to); 84++tot; 85edge[tot].to=to; 86edge[tot].dis=V; 87edge[tot].next=head[from]; 88head[from]=tot; 89} 90queue< int> q; 91bool bfs(int s,int t) 92{ 93for(int i=1; i< =n; ++i) 94deep[i]=inf; 95while(!q.empty())q.pop(); 96for(int i=1; i< =n; ++i)cur[i]=head[i]; 97deep[s]=0; 98q.push(s); 99 100while(!q.empty()) 101{ 102int now=q.front(); q.pop(); 103for(int i=head[now]; i!=-1; i=edge[i].next) 104{ 105if(deep[edge[i].to]==inf& & edge[i].dis) 106{ 107deep[edge[i].to]=deep[now]+1; 108q.push(edge[i].to); 109} 110} 111} 112return deep[t]< inf; 113} 114int dfs(int now,int t,int limit) 115{ 116if(!limit||now==t)return limit; 117int flow=0,f; 118for(int i=cur[now]; i!=-1; i=edge[i].next) 119{ 120cur[now]=i; 121if(deep[edge[i].to]==deep[now]+1& & (f=dfs(edge[i].to,t,min(limit,edge[i].dis)))) 122{ 123flow+=f; 124limit-=f; 125edge[i].dis-=f; 126edge[i^1].dis+=f; 127if(!limit)break; 128} 129} 130return flow; 131} 132void Dinic(int s,int t) 133{ 134while(bfs(s,t)) 135max_flow+=dfs(s,t,inf); 136} 137 }G; 138 struct EDGE 139 { 140int u,v; 141int val; 142friend bool operator< (EDGE a,EDGE b) 143{ 144return a.val< b.val; 145} 146 }edge[M]; 147 148 int main() 149 { 150int n,m; 151sc("%d%d",& n,& m); 152for(int i=1; i< =m; ++i) 153sc("%d%d%d",& edge[i].u,& edge[i].v,& edge[i].val); 154sort(edge+1,edge+1+m); 155int ans=0; 156for(int i=1; i< =m; ++i) 157{ 158G.Init(n); 159for(int j=1; j< i; ++j) 160{ 161if(edge[j].val< edge[i].val) 162G.add(edge[j].u,edge[j].v,1); 163} 164G.Dinic(edge[i].u,edge[i].v); 165ans+=G.max_flow; 166} 167pr("%d ",ans); 168return 0; 169 } 170 171 /**************************************************************************************/ 172 173 int maxx(int a,int b) 174 { 175return a> b?a:b; 176 } 177 178 void swapp(int & a,int & b) 179 { 180a^=b^=a^=b; 181 } 182 183 int lowbit(int n) 184 { 185return n& (-n); 186 } 187 188 int Del_bit_1(int n) 189 { 190return n& (n-1); 191 } 192 193 int abss(int a) 194 { 195return a> 0?a:-a; 196 } 197 198 double fabss(double a) 199 { 200return a> 0?a:-a; 201 } 202 203 int minn(int a,int b) 204 { 205return a< b?a:b; 206 }

【网络流+最小生成树的最少割边数--How Many to Be Happy?】