題意：給出一張有n個(gè)點(diǎn)的圖，有的邊又向，有的邊無向，現(xiàn)在要你破壞一些路，使得從點(diǎn)0無法到達(dá)點(diǎn)n-1。破壞每條路都有一個(gè)代價(jià)。求在代價(jià)最小的前提下，最少需要破壞多少條道路。（就是說求在最小割的前提下，最小的割邊數(shù)）

解題思路：求最小割很好辦，跑一邊最大流即可，但關(guān)鍵是要求最小割邊數(shù)。這里用到了一個(gè)結(jié)論：最小割邊一定滿流，滿流的不一定是最小割邊。先跑一邊最大流，然后把滿流的邊容量設(shè)為1，其它邊容量設(shè)為INF，再跑一邊最大流即可。

自己寫的dinic超時(shí)了，用下別人的代碼吧。。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define INF 1<<30 #define maxn 1010 #define maxm 500000 using namespace std;int v[maxm],Next[maxm],w[maxm]; int first[maxn],d[maxn],q[maxn]; int e,S,T;void init(){e = 0;memset(first,-1,sizeof(first)); }void add_edge(int a,int b,int c){v[e] = b;Next[e] = first[a];w[e] = c;first[a] = e++;v[e] = a;Next[e] = first[b];w[e] = 0;first[b] = e++; }int bfs(){int rear = 0;memset(d,-1,sizeof(d));d[S] = 0;q[rear++] = S;for(int i = 0;i < rear;i++){for(int j = first[q[i]];j != -1;j = Next[j])if(w[j] && d[v[j]] == -1){d[v[j]] = d[q[i]] + 1;q[rear++] = v[j];if(v[j] == T) return 1;}}return 0; }int dfs(int cur,int maxflow){if(cur == T) return maxflow;for(int i = first[cur];i != -1;i = Next[i]){if(w[i] && d[v[i]] == d[cur] + 1)if(int t = dfs(v[i],min(maxflow,w[i]))){w[i] -= t;w[i^1] += t;return t;}}return 0; }int dinic(){int ans = 0;while(bfs()){ans += dfs(S,INF);}return ans; }int main() {int n,m,ncase,cas = 1;scanf("%d",&ncase);while(ncase--){init();scanf("%d%d",&n,&m);S = 0,T = n-1;for(int i = 0;i < m;i++){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);add_edge(a,b,c);if(d == 1) add_edge(b,a,c);}dinic();for(int i = 0;i < e;i += 2){if(w[i] == 0){w[i] = 1;w[i^1] = 0;}else{w[i] = INF;w[i^1] = 0;}}printf("Case %d: %d\n",cas++,dinic());}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 3987(最小割的边数)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。