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
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;
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
#include
#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
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