hdu2435最大流最小割
生活随笔
收集整理的這篇文章主要介紹了
hdu2435最大流最小割
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
2435 ?There is a war
題意:
? ? ? 給你一個有向圖,其中可以有一條邊是無敵的,這條邊可以是圖中的邊,也可以是自己任意加上去的圖中沒有的邊,這條無敵的邊不可以摧毀,讓1和n無法連通的最大摧毀費用,就是1到n的最小割中的最大的那個,這個題卡了好幾天,一開始是各種方法各種wa,后來無意中發現自己犯了個sb錯誤,結果改正后以前的各種方法各種ac,比賽要是碰到這樣的事估計就跪了...
思路:
? ? ?首先能確定的就是題目要求咱們就最小割(最大流 = 最小割),但關鍵是有那么一條無堅不摧的nb道路,所以一開始的想法肯定是暴力枚舉N*N的邊,直接TLE出翔了,那么就優化,記得以前的一道題目 給你一個圖求刪除其中一條邊最短路中最大的那個,答案是只枚舉最短路上的邊就可以了, 這個題目也是類似,只要枚舉最小割后兩個集合的點組成的邊就行了,因為假如點a和點b是一個集合的,那么把邊ab變成無敵的沒有意思,最小割的值不會改變,,那么怎么吧分成兩個集合呢,兩種方法,一個是深搜,這個方法容易理解,先跑一遍最大流,然后從點1開始深搜,如果當前點走過或者沒有流量了(跑完一遍最大流后的流量),直接continue,這樣被mark的點就是左集合的點,剩下的就是右集合的點,還有一種方法就是直接看DINIC后的deep數組,如果不等于-1就是左集合的,否則的就是右集合的,這個我結論是網上的,我還不知道為什么,分成兩個集合后就可以枚舉兩個集合的點建枚舉的邊了,這塊也有兩個方法,一個就是之前不是跑一邊最大流了嗎,加上當前枚舉邊,直接在殘余網絡上跑,取得最大的max最后輸出一開始那個最大流maxflow+max,(記得每次跑之前都還原成第一次跑完的殘余網路),第二種方法就是直接重新建邊,一開始的時候吧m條邊記錄下來,每次枚舉都重新建圖,然后加上枚舉的邊跑,最后輸出的是最大流中最大的那個maxflow.下面是三種方法的代碼..
深搜找源集和匯集,在殘余網絡上跑 15ms AC
#include<stdio.h>
#include<string.h>
#include<queue>
#define inf 1000000000
? ?int to ,next ,cost;
}STAR;
typedef struct
{
? ?int x ,t;
}DEP;
STAR E[N_edge] ,E_[N_edge];
DEP xin ,tou;
int list[N_node] ,list1[N_node] ,tot;
int list2[N_node];
int deep[N_node];
int mks[N_node] ,mks_;
int mkh[N_node] ,mkh_;
int mark[N_node];
void add(int a ,int b ,int c)
{
? ?E[++tot].to = b;
? ?E[tot].cost = c;
? ?E[tot].next = list[a];
? ?list[a] = tot;
? ?
? ?E[++tot].to = a;
? ?E[tot].cost = 0;
? ?E[tot].next = list[b];
? ?list[b] = tot;
}
int minn(int a ,int b)
{
? ?return a < b ? a : b;
}
bool BFS_DEEP(int s ,int t ,int n)
{
? ? memset(deep ,255 ,sizeof(deep));
? ? deep[s] = 0;
? ? xin.x = s;
? ? xin.t = 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 ++)
? ?list1[i] = list[i];
? ?return deep[t] != -1;
}
int DFS_MAX_FLOW(int s ,int t ,int flow)
{
? ?if(s == t) return flow;
? ?int nowflow = 0;
? ?for(int k = list1[s] ;k ;k = E[k].next)
? ?{
? ? ? list1[s] = k;
? ? ? int to = E[k].to;
? ? ? int c = E[k].cost;
? ? ? if(deep[to] != deep[s] + 1||!E[k].cost)
? ? ? continue;
? ? ? int tmp = DFS_MAX_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;
}
int DINIC(int s ,int t ,int n)
{
? ?int ans = 0;
? ?while(BFS_DEEP(s ,t ,n))
? ?{
? ? ? ans += DFS_MAX_FLOW(s ,t ,inf);
? ?}
? ?return ans;
}
void DFS(int s)
{
? ?for(int k = list[s] ;k ;k = E[k].next)
? ?{
? ? ? int to = E[k].to;
? ? ? if(mark[to] || !E[k].cost)
? ? ? continue;
? ? ? mark[to] = 1;
? ? ? DFS(to);
? ?}
? ?return ;
}
int main ()
{
? ?int n ,m ,i ,j ,t;
? ?int a ,b ,c;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? memset(list ,0 ,sizeof(list));
? ? ? tot = 1;
? ? ? scanf("%d %d" ,&n ,&m);
? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? {
? ? ? ? ?scanf("%d %d %d" ,&a ,&b ,&c);
? ? ? ? ?add(a ,b ,c);
? ? ? }
? ? ? int ans = DINIC(1 ,n ,n);
? ? ? mks_ = mkh_ = 0;
? ? ? memset(mark ,0 ,sizeof(mark));
? ? ? mark[1] = 1;
? ? ? DFS(1);
? ? ? for(i = 2 ;i < n ;i ++)
? ? ? if(mark[i]) mks[++mks_] = i;
? ? ? else mkh[++mkh_] = i;
? ? ??
? ? ? for(i = 1 ;i <= tot ;i ++)
? ? ? E_[i] = E[i];
? ? ? int mktot = tot;
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? list2[i] = list[i];
? ? ??
? ? ? int max = 0;
? ? ? for(i = 1 ;i <= mks_ ;i ++)
? ? ? for(j = 1 ;j <= mkh_ ;j ++)
? ? ? {
? ? ? ? ?a = mks[i] ,b = mkh[j];
? ? ? ? ?for(int k = 1 ;k <= mktot ;k ++)
? ? ? ? ?E[k] = E_[k];
? ? ? ? ?memset(list ,0 ,sizeof(list));
? ? ? ? ?for(int k = 1 ;k <= n ;k ++)
? ? ? ? ?list[k] = list2[k];
? ? ? ? ?tot = mktot;
? ? ? ? ?add(a ,b ,inf);
? ? ? ? ?int tmp = DINIC(1 ,n ,n);
? ? ? ? ?if(max < tmp) max = tmp;
? ? ? }
? ? ? printf("%d\n" ,ans + max);
? ?}
? ?return 0;
}
? ? ? ? ?
? ? ? ? ?
? ? ??
? ? ??
根據deep數組找源集和匯集,在殘余網絡上跑 31ms AC
#include<stdio.h>
#include<string.h>
#include<queue>
#define N_node 120
#define N_edge 22000
#define inf 1000000000
using namespace std;
typedef struct
{
? ?int to ,next ,cost;
}STAR;
typedef struct
{
? ?int x ,t;
}DEP;
STAR E[N_edge] ,E_[N_edge];
DEP xin ,tou;
int list[N_node] ,list1[N_node] ,tot;
int list2[N_node];
int deep[N_node];
int mks[N_node] ,mks_;
int mkh[N_node] ,mkh_;
void add(int a ,int b ,int c)
{
? ?E[++tot].to = b;
? ?E[tot].cost = c;
? ?E[tot].next = list[a];
? ?list[a] = tot;
? ?
? ?E[++tot].to = a;
? ?E[tot].cost = 0;
? ?E[tot].next = list[b];
? ?list[b] = tot;
}
int minn(int a ,int b)
{
? ?return a < b ? a : b;
}
bool BFS_DEEP(int s ,int t ,int n)
{
? ? memset(deep ,255 ,sizeof(deep));
? ? deep[s] = 0;
? ? xin.x = s;
? ? xin.t = 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 ++)
? ?list1[i] = list[i];
? ?return deep[t] != -1;
}
int DFS_MAX_FLOW(int s ,int t ,int flow)
{
? ?if(s == t) return flow;
? ?int nowflow = 0;
? ?for(int k = list1[s] ;k ;k = E[k].next)
? ?{
? ? ? list1[s] = k;
? ? ? int to = E[k].to;
? ? ? int c = E[k].cost;
? ? ? if(deep[to] != deep[s] + 1||!E[k].cost)
? ? ? continue;
? ? ? int tmp = DFS_MAX_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;
}
int DINIC(int s ,int t ,int n)
{
? ?int ans = 0;
? ?while(BFS_DEEP(s ,t ,n))
? ?{
? ? ? ans += DFS_MAX_FLOW(s ,t ,inf);
? ?}
? ?return ans;
}
int main ()
{
? ?int n ,m ,i ,j ,t;
? ?int a ,b ,c;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? memset(list ,0 ,sizeof(list));
? ? ? tot = 1;
? ? ? scanf("%d %d" ,&n ,&m);
? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? {
? ? ? ? ?scanf("%d %d %d" ,&a ,&b ,&c);
? ? ? ? ?add(a ,b ,c);
? ? ? }
? ? ? int ans = DINIC(1 ,n ,n);
? ? ? mks_ = mkh_ = 0;
? ? ? for(i = 2 ;i < n ;i ++)
? ? ? if(deep[i] != -1) mks[++mks_] = i;
? ? ? else mkh[++mkh_] = i;
? ? ??
? ? ? for(i = 1 ;i <= tot ;i ++)
? ? ? E_[i] = E[i];
? ? ? int mktot = tot;
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? list2[i] = list[i];
? ? ??
? ? ? int max = 0;
? ? ? for(i = 1 ;i <= mks_ ;i ++)
? ? ? for(j = 1 ;j <= mkh_ ;j ++)
? ? ? {
? ? ? ? ?a = mks[i] ,b = mkh[j];
? ? ? ? ?for(int k = 1 ;k <= mktot ;k ++)
? ? ? ? ?E[k] = E_[k];
? ? ? ? ?memset(list ,0 ,sizeof(list));
? ? ? ? ?for(int k = 1 ;k <= n ;k ++)
? ? ? ? ?list[k] = list2[k];
? ? ? ? ?tot = mktot;
? ? ? ? ?add(a ,b ,inf);
? ? ? ? ?int tmp = DINIC(1 ,n ,n);
? ? ? ? ?if(max < tmp) max = tmp;
? ? ? }
? ? ? printf("%d\n" ,ans + max);
? ?}
? ?return 0;
}
? ? ? ? ?
直接重新建圖,深搜找源集和匯集(容易理解) 15msAC
#include<string.h>
#include<queue>
#define N_node 120
#define N_edge 22000
#define inf 1000000000
using namespace std;
typedef struct
{
? ?int to ,next ,cost;
}STAR;
typedef struct
{
? ?int x ,t;
}DEP;
typedef struct
{
? ?int a ,b ,c;
}EDGE;
STAR E[N_edge];
EDGE edge[N_edge];
DEP xin ,tou;
int list[N_node] ,list1[N_node] ,tot;
int deep[N_node];
int mks[N_node] ,mks_;
int mkh[N_node] ,mkh_;
int mark[N_node];
void add(int a ,int b ,int c)
{
? ?E[++tot].to = b;
? ?E[tot].cost = c;
? ?E[tot].next = list[a];
? ?list[a] = tot;
? ?
? ?E[++tot].to = a;
? ?E[tot].cost = 0;
? ?E[tot].next = list[b];
? ?list[b] = tot;
}
int minn(int a ,int b)
{
? ?return a < b ? a : b;
}
bool BFS_DEEP(int s ,int t ,int n)
{
? ? memset(deep ,255 ,sizeof(deep));
? ? deep[s] = 0;
? ? xin.x = s;
? ? xin.t = 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 ++)
? ?list1[i] = list[i];
? ?return deep[t] != -1;
}
int DFS_MAX_FLOW(int s ,int t ,int flow)
{
? ?if(s == t) return flow;
? ?int nowflow = 0;
? ?for(int k = list1[s] ;k ;k = E[k].next)
? ?{
? ? ? list1[s] = k;
? ? ? int to = E[k].to;
? ? ? int c = E[k].cost;
? ? ? if(deep[to] != deep[s] + 1||!E[k].cost)
? ? ? continue;
? ? ? int tmp = DFS_MAX_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;
}
int DINIC(int s ,int t ,int n)
{
? ?int ans = 0;
? ?while(BFS_DEEP(s ,t ,n))
? ?{
? ? ? ans += DFS_MAX_FLOW(s ,t ,inf);
? ?}
? ?return ans;
}
void DFS(int s)
{
? ?for(int k = list[s] ;k ;k = E[k].next)
? ?{
? ? ? int to = E[k].to;
? ? ? if(mark[to] || !E[k].cost)
? ? ? continue;
? ? ? mark[to] = 1;
? ? ? DFS(to);
? ?}
? ?return ;
}
int main ()
{
? ?int n ,m ,i ,j ,t;
? ?int a ,b ,c;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? memset(list ,0 ,sizeof(list));
? ? ? tot = 1;
? ? ? scanf("%d %d" ,&n ,&m);
? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? {
? ? ? ? ?scanf("%d %d %d" ,&a ,&b ,&c);
? ? ? ? ?add(a ,b ,c);
? ? ? ? ?edge[i].a = a ,edge[i].b = b ,edge[i].c = c;
? ? ? }
? ? ? int ans = DINIC(1 ,n ,n);
? ? ? mks_ = mkh_ = 0;
? ? ? memset(mark ,0 ,sizeof(mark));
? ? ? mark[1] = 1;
? ? ? DFS(1);
? ? ? for(i = 2 ;i < n ;i ++)
? ? ? if(mark[i]) mks[++mks_] = i;
? ? ? else mkh[++mkh_] = i;
? ? ? for(i = 1 ;i <= mks_ ;i ++)
? ? ? for(j = 1 ;j <= mkh_ ;j ++)
? ? ? {
? ? ? ? ?a = mks[i] ,b = mkh[j];
? ? ? ? ?memset(list ,0 ,sizeof(list));
? ? ? ? ?tot = 1;
? ? ? ? ?for(int k = 1 ;k <= m ;k ++)
? ? ? ? ?add(edge[k].a ,edge[k].b ,edge[k].c);
? ? ? ? ?add(a ,b ,inf);
? ? ? ? ?int tmp = DINIC(1 ,n ,n);
? ? ? ? ?if(ans < tmp) ans = tmp;
? ? ? }
? ? ? printf("%d\n" ,ans);
? ?}
? ?return 0;
}
題意:
? ? ? 給你一個有向圖,其中可以有一條邊是無敵的,這條邊可以是圖中的邊,也可以是自己任意加上去的圖中沒有的邊,這條無敵的邊不可以摧毀,讓1和n無法連通的最大摧毀費用,就是1到n的最小割中的最大的那個,這個題卡了好幾天,一開始是各種方法各種wa,后來無意中發現自己犯了個sb錯誤,結果改正后以前的各種方法各種ac,比賽要是碰到這樣的事估計就跪了...
思路:
? ? ?首先能確定的就是題目要求咱們就最小割(最大流 = 最小割),但關鍵是有那么一條無堅不摧的nb道路,所以一開始的想法肯定是暴力枚舉N*N的邊,直接TLE出翔了,那么就優化,記得以前的一道題目 給你一個圖求刪除其中一條邊最短路中最大的那個,答案是只枚舉最短路上的邊就可以了, 這個題目也是類似,只要枚舉最小割后兩個集合的點組成的邊就行了,因為假如點a和點b是一個集合的,那么把邊ab變成無敵的沒有意思,最小割的值不會改變,,那么怎么吧分成兩個集合呢,兩種方法,一個是深搜,這個方法容易理解,先跑一遍最大流,然后從點1開始深搜,如果當前點走過或者沒有流量了(跑完一遍最大流后的流量),直接continue,這樣被mark的點就是左集合的點,剩下的就是右集合的點,還有一種方法就是直接看DINIC后的deep數組,如果不等于-1就是左集合的,否則的就是右集合的,這個我結論是網上的,我還不知道為什么,分成兩個集合后就可以枚舉兩個集合的點建枚舉的邊了,這塊也有兩個方法,一個就是之前不是跑一邊最大流了嗎,加上當前枚舉邊,直接在殘余網絡上跑,取得最大的max最后輸出一開始那個最大流maxflow+max,(記得每次跑之前都還原成第一次跑完的殘余網路),第二種方法就是直接重新建邊,一開始的時候吧m條邊記錄下來,每次枚舉都重新建圖,然后加上枚舉的邊跑,最后輸出的是最大流中最大的那個maxflow.下面是三種方法的代碼..
深搜找源集和匯集,在殘余網絡上跑 15ms AC
#include<stdio.h>
#include<string.h>
#include<queue>
#define N_node 120
#define N_edge 22000#define inf 1000000000
using namespace std;
typedef struct
{? ?int to ,next ,cost;
}STAR;
typedef struct
{
? ?int x ,t;
}DEP;
STAR E[N_edge] ,E_[N_edge];
DEP xin ,tou;
int list[N_node] ,list1[N_node] ,tot;
int list2[N_node];
int deep[N_node];
int mks[N_node] ,mks_;
int mkh[N_node] ,mkh_;
int mark[N_node];
void add(int a ,int b ,int c)
{
? ?E[++tot].to = b;
? ?E[tot].cost = c;
? ?E[tot].next = list[a];
? ?list[a] = tot;
? ?
? ?E[++tot].to = a;
? ?E[tot].cost = 0;
? ?E[tot].next = list[b];
? ?list[b] = tot;
}
int minn(int a ,int b)
{
? ?return a < b ? a : b;
}
bool BFS_DEEP(int s ,int t ,int n)
{
? ? memset(deep ,255 ,sizeof(deep));
? ? deep[s] = 0;
? ? xin.x = s;
? ? xin.t = 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 ++)
? ?list1[i] = list[i];
? ?return deep[t] != -1;
}
int DFS_MAX_FLOW(int s ,int t ,int flow)
{
? ?if(s == t) return flow;
? ?int nowflow = 0;
? ?for(int k = list1[s] ;k ;k = E[k].next)
? ?{
? ? ? list1[s] = k;
? ? ? int to = E[k].to;
? ? ? int c = E[k].cost;
? ? ? if(deep[to] != deep[s] + 1||!E[k].cost)
? ? ? continue;
? ? ? int tmp = DFS_MAX_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;
}
int DINIC(int s ,int t ,int n)
{
? ?int ans = 0;
? ?while(BFS_DEEP(s ,t ,n))
? ?{
? ? ? ans += DFS_MAX_FLOW(s ,t ,inf);
? ?}
? ?return ans;
}
void DFS(int s)
{
? ?for(int k = list[s] ;k ;k = E[k].next)
? ?{
? ? ? int to = E[k].to;
? ? ? if(mark[to] || !E[k].cost)
? ? ? continue;
? ? ? mark[to] = 1;
? ? ? DFS(to);
? ?}
? ?return ;
}
int main ()
{
? ?int n ,m ,i ,j ,t;
? ?int a ,b ,c;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? memset(list ,0 ,sizeof(list));
? ? ? tot = 1;
? ? ? scanf("%d %d" ,&n ,&m);
? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? {
? ? ? ? ?scanf("%d %d %d" ,&a ,&b ,&c);
? ? ? ? ?add(a ,b ,c);
? ? ? }
? ? ? int ans = DINIC(1 ,n ,n);
? ? ? mks_ = mkh_ = 0;
? ? ? memset(mark ,0 ,sizeof(mark));
? ? ? mark[1] = 1;
? ? ? DFS(1);
? ? ? for(i = 2 ;i < n ;i ++)
? ? ? if(mark[i]) mks[++mks_] = i;
? ? ? else mkh[++mkh_] = i;
? ? ??
? ? ? for(i = 1 ;i <= tot ;i ++)
? ? ? E_[i] = E[i];
? ? ? int mktot = tot;
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? list2[i] = list[i];
? ? ??
? ? ? int max = 0;
? ? ? for(i = 1 ;i <= mks_ ;i ++)
? ? ? for(j = 1 ;j <= mkh_ ;j ++)
? ? ? {
? ? ? ? ?a = mks[i] ,b = mkh[j];
? ? ? ? ?for(int k = 1 ;k <= mktot ;k ++)
? ? ? ? ?E[k] = E_[k];
? ? ? ? ?memset(list ,0 ,sizeof(list));
? ? ? ? ?for(int k = 1 ;k <= n ;k ++)
? ? ? ? ?list[k] = list2[k];
? ? ? ? ?tot = mktot;
? ? ? ? ?add(a ,b ,inf);
? ? ? ? ?int tmp = DINIC(1 ,n ,n);
? ? ? ? ?if(max < tmp) max = tmp;
? ? ? }
? ? ? printf("%d\n" ,ans + max);
? ?}
? ?return 0;
}
? ? ? ? ?
? ? ? ? ?
? ? ??
? ? ??
根據deep數組找源集和匯集,在殘余網絡上跑 31ms AC
#include<stdio.h>
#include<string.h>
#include<queue>
#define N_node 120
#define N_edge 22000
#define inf 1000000000
using namespace std;
typedef struct
{
? ?int to ,next ,cost;
}STAR;
typedef struct
{
? ?int x ,t;
}DEP;
STAR E[N_edge] ,E_[N_edge];
DEP xin ,tou;
int list[N_node] ,list1[N_node] ,tot;
int list2[N_node];
int deep[N_node];
int mks[N_node] ,mks_;
int mkh[N_node] ,mkh_;
void add(int a ,int b ,int c)
{
? ?E[++tot].to = b;
? ?E[tot].cost = c;
? ?E[tot].next = list[a];
? ?list[a] = tot;
? ?
? ?E[++tot].to = a;
? ?E[tot].cost = 0;
? ?E[tot].next = list[b];
? ?list[b] = tot;
}
int minn(int a ,int b)
{
? ?return a < b ? a : b;
}
bool BFS_DEEP(int s ,int t ,int n)
{
? ? memset(deep ,255 ,sizeof(deep));
? ? deep[s] = 0;
? ? xin.x = s;
? ? xin.t = 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 ++)
? ?list1[i] = list[i];
? ?return deep[t] != -1;
}
int DFS_MAX_FLOW(int s ,int t ,int flow)
{
? ?if(s == t) return flow;
? ?int nowflow = 0;
? ?for(int k = list1[s] ;k ;k = E[k].next)
? ?{
? ? ? list1[s] = k;
? ? ? int to = E[k].to;
? ? ? int c = E[k].cost;
? ? ? if(deep[to] != deep[s] + 1||!E[k].cost)
? ? ? continue;
? ? ? int tmp = DFS_MAX_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;
}
int DINIC(int s ,int t ,int n)
{
? ?int ans = 0;
? ?while(BFS_DEEP(s ,t ,n))
? ?{
? ? ? ans += DFS_MAX_FLOW(s ,t ,inf);
? ?}
? ?return ans;
}
int main ()
{
? ?int n ,m ,i ,j ,t;
? ?int a ,b ,c;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? memset(list ,0 ,sizeof(list));
? ? ? tot = 1;
? ? ? scanf("%d %d" ,&n ,&m);
? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? {
? ? ? ? ?scanf("%d %d %d" ,&a ,&b ,&c);
? ? ? ? ?add(a ,b ,c);
? ? ? }
? ? ? int ans = DINIC(1 ,n ,n);
? ? ? mks_ = mkh_ = 0;
? ? ? for(i = 2 ;i < n ;i ++)
? ? ? if(deep[i] != -1) mks[++mks_] = i;
? ? ? else mkh[++mkh_] = i;
? ? ??
? ? ? for(i = 1 ;i <= tot ;i ++)
? ? ? E_[i] = E[i];
? ? ? int mktot = tot;
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? list2[i] = list[i];
? ? ??
? ? ? int max = 0;
? ? ? for(i = 1 ;i <= mks_ ;i ++)
? ? ? for(j = 1 ;j <= mkh_ ;j ++)
? ? ? {
? ? ? ? ?a = mks[i] ,b = mkh[j];
? ? ? ? ?for(int k = 1 ;k <= mktot ;k ++)
? ? ? ? ?E[k] = E_[k];
? ? ? ? ?memset(list ,0 ,sizeof(list));
? ? ? ? ?for(int k = 1 ;k <= n ;k ++)
? ? ? ? ?list[k] = list2[k];
? ? ? ? ?tot = mktot;
? ? ? ? ?add(a ,b ,inf);
? ? ? ? ?int tmp = DINIC(1 ,n ,n);
? ? ? ? ?if(max < tmp) max = tmp;
? ? ? }
? ? ? printf("%d\n" ,ans + max);
? ?}
? ?return 0;
}
? ? ? ? ?
直接重新建圖,深搜找源集和匯集(容易理解) 15msAC
#include<string.h>
#include<queue>
#define N_node 120
#define N_edge 22000
#define inf 1000000000
using namespace std;
typedef struct
{
? ?int to ,next ,cost;
}STAR;
typedef struct
{
? ?int x ,t;
}DEP;
typedef struct
{
? ?int a ,b ,c;
}EDGE;
STAR E[N_edge];
EDGE edge[N_edge];
DEP xin ,tou;
int list[N_node] ,list1[N_node] ,tot;
int deep[N_node];
int mks[N_node] ,mks_;
int mkh[N_node] ,mkh_;
int mark[N_node];
void add(int a ,int b ,int c)
{
? ?E[++tot].to = b;
? ?E[tot].cost = c;
? ?E[tot].next = list[a];
? ?list[a] = tot;
? ?
? ?E[++tot].to = a;
? ?E[tot].cost = 0;
? ?E[tot].next = list[b];
? ?list[b] = tot;
}
int minn(int a ,int b)
{
? ?return a < b ? a : b;
}
bool BFS_DEEP(int s ,int t ,int n)
{
? ? memset(deep ,255 ,sizeof(deep));
? ? deep[s] = 0;
? ? xin.x = s;
? ? xin.t = 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 ++)
? ?list1[i] = list[i];
? ?return deep[t] != -1;
}
int DFS_MAX_FLOW(int s ,int t ,int flow)
{
? ?if(s == t) return flow;
? ?int nowflow = 0;
? ?for(int k = list1[s] ;k ;k = E[k].next)
? ?{
? ? ? list1[s] = k;
? ? ? int to = E[k].to;
? ? ? int c = E[k].cost;
? ? ? if(deep[to] != deep[s] + 1||!E[k].cost)
? ? ? continue;
? ? ? int tmp = DFS_MAX_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;
}
int DINIC(int s ,int t ,int n)
{
? ?int ans = 0;
? ?while(BFS_DEEP(s ,t ,n))
? ?{
? ? ? ans += DFS_MAX_FLOW(s ,t ,inf);
? ?}
? ?return ans;
}
void DFS(int s)
{
? ?for(int k = list[s] ;k ;k = E[k].next)
? ?{
? ? ? int to = E[k].to;
? ? ? if(mark[to] || !E[k].cost)
? ? ? continue;
? ? ? mark[to] = 1;
? ? ? DFS(to);
? ?}
? ?return ;
}
int main ()
{
? ?int n ,m ,i ,j ,t;
? ?int a ,b ,c;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? memset(list ,0 ,sizeof(list));
? ? ? tot = 1;
? ? ? scanf("%d %d" ,&n ,&m);
? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? {
? ? ? ? ?scanf("%d %d %d" ,&a ,&b ,&c);
? ? ? ? ?add(a ,b ,c);
? ? ? ? ?edge[i].a = a ,edge[i].b = b ,edge[i].c = c;
? ? ? }
? ? ? int ans = DINIC(1 ,n ,n);
? ? ? mks_ = mkh_ = 0;
? ? ? memset(mark ,0 ,sizeof(mark));
? ? ? mark[1] = 1;
? ? ? DFS(1);
? ? ? for(i = 2 ;i < n ;i ++)
? ? ? if(mark[i]) mks[++mks_] = i;
? ? ? else mkh[++mkh_] = i;
? ? ? for(i = 1 ;i <= mks_ ;i ++)
? ? ? for(j = 1 ;j <= mkh_ ;j ++)
? ? ? {
? ? ? ? ?a = mks[i] ,b = mkh[j];
? ? ? ? ?memset(list ,0 ,sizeof(list));
? ? ? ? ?tot = 1;
? ? ? ? ?for(int k = 1 ;k <= m ;k ++)
? ? ? ? ?add(edge[k].a ,edge[k].b ,edge[k].c);
? ? ? ? ?add(a ,b ,inf);
? ? ? ? ?int tmp = DINIC(1 ,n ,n);
? ? ? ? ?if(ans < tmp) ans = tmp;
? ? ? }
? ? ? printf("%d\n" ,ans);
? ?}
? ?return 0;
}
總結
以上是生活随笔為你收集整理的hdu2435最大流最小割的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： hdu3665 水最短路
- 下一篇： hdu4267线段树段更新,点查找,55