题目链接：https://vjudge.net/problem/POJ-2531

最大流-最小割问题：

https://wenku.baidu.com/view/54323c030722192e4536f64f.html

题意：给出n个点(0-n-1)，接下来n行，每行有n个数，第i行代表第i-1个数距离n个点的距离，问将这些点分为两部分，两个点集之间的权值最大值为多少。例如样例中讲0,1,2分为两部分（1，3）和（2）两部分，则最长距离为map[1][2]+map[3][2]=90。

https://blog.csdn.net/u013486414/article/details/43890357

代码实现：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>

using namespace std;
const int inf=0x3f3f3f3f;
int map[40][40];
int g[40];
int n,res;
void dfs(int site,int sum)
{
???int i;
???g[site]=1;//取出点
???int num=sum;
???for(i=0;i<n;i++){
???????if(g[i]==1)//与site在一个集合里的点
???????????num-=map[site][i];//减去他们之间的权值
???????else//否则和site不在一个集合里
???????????num+=map[site][i];//加上他们之间的权值
???}
???res=max(res,num);//依次循环结束找到的最大值
???for(i=site+1;i<n;i++){//然后遍历剩下的点
???????if(num>sum){//小剪枝，如果加入了点site后两个集合之间的权值小了，则就不需要遍历这个点。
???????????dfs(i,num);
???????????g[i]=0;
???????}
???}

}
int main()
{
???int i,j;
???while(~scanf("%d",&n)){
???????memset(map,0,sizeof(map));
???????memset(g,0,sizeof(g));
???????for(i=0;i<n;i++)
???????????for(j=0;j<n;j++)
???????????scanf("%d",&map[i][j]);
???????????res=-inf;
???????????dfs(0,0);
???????????printf("%d\n",res);
???}
???return 0;
}

POJ 2531-Network Saboteur(dfs)

原文地址：https://www.cnblogs.com/LJHAHA/p/10325959.html