題意：
? ? ? 是讓你求最小割之后問最小割的最少邊數是多少，因為最小割不是唯一的，所以存在最小邊數的問法。


思路：
? ? ? 兩個方法，一個是先一遍最大流，然后把割邊全都改成流量1，其他的全都改成流量無窮就行了，第二個方法是比較經典的方法，就是把權值放大 *（E+1）+1,最后在對（E+1）取余就行了，這么干其實是同時跑了兩遍最大流，只不過是兩個權值之間的差距太大，不會相互影響。



#include<queue>
#include<stdio.h>
#include<string.h>

#define N_node 1000 + 5
#define N_edge 400000 + 100
#define INF 2055000000

using namespace std;

typedef struct
{
? ?int from ,to ,next;
? ?long long ?cost;
}STAR;

typedef struct
{
? ?int x ,t;
}DEP;

STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,list2[N_node] ,tot;
int deep[N_node];

void add(int a ,int b ,long long c)
{
? ?E[++tot].from = a;
? ?E[tot].to = b;
? ?E[tot].cost = c;
? ?E[tot].next = list[a];
? ?list[a] = tot;
? ?
? ?E[++tot].from = b;
? ?E[tot].to = a;
? ?E[tot].cost = 0;
? ?E[tot].next = list[b];
? ?list[b] = tot;
}

long long minn(long long a ,long long b)
{
? ?return a < b ? a : b;
}

bool BFS_Deep(int s ,int t ,int n)
{
? ?memset(deep ,255 ,sizeof(deep));
? ?xin.x = s ,xin.t = 0;
? ?deep[s] = 0;
? ?queue<DEP>q;
? ?q.push(xin);
? ?while(!q.empty())
? ?{
? ? ? tou = q.front();
? ? ? q.pop();
? ? ??
? ? ? for(int k = list[tou.x] ;k ;k = E[k].next)
? ? ? {
? ? ? ? ?xin.x = E[k].to;
? ? ? ? ?xin.t = tou.t + 1;
? ? ? ? ?if(deep[xin.x] != -1 || !E[k].cost)
? ? ? ? ?continue;
? ? ? ? ?deep[xin.x] = xin.t;
? ? ? ? ?q.push(xin);
? ? ? }
? ?}
? ?for(int i = 0 ;i <= n ;i ++)
? ?list2[i] = list[i];
? ?return deep[t] != -1;
}

long long DFS_Flow(int s ,int t ,long long flow)
{
? ?if(s == t) return flow;
? ?long long nowflow = 0;
? ?for(int k = list2[s] ;k ;k = E[k].next)
? ?{
? ? ? list2[s] = k;
? ? ? int to = E[k].to;
? ? ? long long c = E[k].cost;
? ? ? if(deep[to] != deep[s] + 1 || !c) continue;
? ? ? long long tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));
? ? ? nowflow += tmp;
? ? ? E[k].cost -= tmp;
? ? ? E[k^1].cost += tmp;
? ? ? if(nowflow == flow) break;
? ?}
? ?if(!nowflow) deep[s] = 0;
? ?return nowflow;
}

long long DINIC(int s ,int t ,int n)

{
? ?long long Ans = 0;
? ?while(BFS_Deep(s ,t ,n))
? ?{
? ? ? Ans += DFS_Flow(s ,t ,INF);
? ?}
? ?return Ans;
}

int main ()
{
? ? int a ,b ,c ,d;
? ? int t ,n ,m ,i ,cas = 1;
? ? scanf("%d" ,&t);
? ? while(t--)
? ? {
? ? ? ? scanf("%d %d" ,&n ,&m);
? ? ? ? memset(list ,0 ,sizeof(list));
? ? ? ? tot = 1;
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ?scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);
? ? ? ? ? ?if(d) add(a + 1 ,b + 1 ,(long long)c) ,add(b + 1 ,a + 1 ,c);
? ? ? ? ? ?else add(a + 1 ,b + 1 ,(long long)c);
? ? ? ? }
? ? ? ? DINIC(1 ,n ,n);
? ? ? ? for(i = 2 ;i <= tot ;i += 2)
? ? ? ? if(!E[i].cost) E[i].cost = 1 ,E[i^1].cost = 0;
? ? ? ? else E[i].cost = INF ,E[i^1].cost = 0;
? ? ? ? printf("Case %d: %lld\n" ,cas ++ ,DINIC(1 ,n ,n));
? ? ?}
? ? ?return 0;
} ? ??
? ??


#include<queue>
#include<stdio.h>
#include<string.h>

#define N_node 1000 + 5
#define N_edge 400000 + 100
#define INF 205500000000000//這個地方記得開大點，因為放大了權值

using namespace std;

typedef struct
{
? ?int from ,to ,next;
? ?long long ?cost;
}STAR;

typedef struct
{
? ?int x ,t;
}DEP;

STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,list2[N_node] ,tot;
int deep[N_node];

void add(int a ,int b ,long long c)
{
? ?E[++tot].from = a;
? ?E[tot].to = b;
? ?E[tot].cost = c;
? ?E[tot].next = list[a];
? ?list[a] = tot;

? ?

? ?E[++tot].from = b;

? ?E[tot].to = a;
? ?E[tot].cost = 0;
? ?E[tot].next = list[b];
? ?list[b] = tot;
}

long long minn(long long a ,long long b)
{
? ?return a < b ? a : b;
}

bool BFS_Deep(int s ,int t ,int n)
{
? ?memset(deep ,255 ,sizeof(deep));
? ?xin.x = s ,xin.t = 0;
? ?deep[s] = 0;
? ?queue<DEP>q;
? ?q.push(xin);
? ?while(!q.empty())
? ?{
? ? ? tou = q.front();
? ? ? q.pop();
? ? ??
? ? ? for(int k = list[tou.x] ;k ;k = E[k].next)
? ? ? {
? ? ? ? ?xin.x = E[k].to;
? ? ? ? ?xin.t = tou.t + 1;
? ? ? ? ?if(deep[xin.x] != -1 || !E[k].cost)
? ? ? ? ?continue;
? ? ? ? ?deep[xin.x] = xin.t;
? ? ? ? ?q.push(xin);
? ? ? }
? ?}
? ?for(int i = 0 ;i <= n ;i ++)
? ?list2[i] = list[i];
? ?return deep[t] != -1;
}

long long DFS_Flow(int s ,int t ,long long flow)
{
? ?if(s == t) return flow;
? ?long long nowflow = 0;
? ?for(int k = list2[s] ;k ;k = E[k].next)
? ?{
? ? ? list2[s] = k;
? ? ? int to = E[k].to;
? ? ? long long c = E[k].cost;
? ? ? if(deep[to] != deep[s] + 1 || !c) continue;
? ? ? long long tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));
? ? ? nowflow += tmp;
? ? ? E[k].cost -= tmp;
? ? ? E[k^1].cost += tmp;
? ? ? if(nowflow == flow) break;
? ?}
? ?if(!nowflow) deep[s] = 0;
? ?return nowflow;
}

long long DINIC(int s ,int t ,int n)
{
? ?long long Ans = 0;
? ?while(BFS_Deep(s ,t ,n))
? ?{
? ? ? Ans += DFS_Flow(s ,t ,INF);
? ?}
? ?return Ans;
}

int main ()
{
? ? int a ,b ,c ,d;
? ? int t ,n ,m ,i ,cas = 1;
? ? scanf("%d" ,&t);
? ? while(t--)
? ? {
? ? ? ? scanf("%d %d" ,&n ,&m);
? ? ? ? memset(list ,0 ,sizeof(list));
? ? ? ? tot = 1;
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ?scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);
? ? ? ? ? ?if(d) add(a + 1 ,b + 1 ,(long long)c * 100001 + 1) ,add(b + 1 ,a +?1 ,(long long)c * 100001 + 1);
? ? ? ? ? ?else add(a + 1 ,b + 1 ,(long long)c * 100001 + 1);
? ? ? ? }
? ? ? ? printf("Case %d: %lld\n" ,cas ++ ,DINIC(1 ,n ,n) % 100001);
? ? ?}
? ? ?return 0;
} ? ??
? ??
? ??
? ??
? ??




? ??
? ??
? ??

總結

以上是生活随笔為你收集整理的hdu3987 最小割边数的全部內容，希望文章能夠幫你解決所遇到的問題。

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