Poj 2531 Network Saboteur (DFS/二进制枚举集合)

亦凉 2023-01-05 05:13 124阅读 0赞

题意：把一个完全图分成两部分，使得连接这两部分边的权和最大。  
思路：图论的无向完全图的最大割问题

用了两种方法。

#include <cstdio>
    #include <cstring>
    
    int n;
    int data[25][25];
    int belong[25];
    int ans;
    
    void DFS (int a,int sum)
    {
    	if (a==n)
    	{
    		if (sum>ans) ans=sum;
    		return ;
    	}
    	int temp=0,i;
    	for (i=0;i<a;i++)
    		if (belong[i]==2)
    			temp+=data[a][i];
    	belong[a]=1;
    	DFS(a+1,sum+temp);
    	temp=0;
    	for (i=0;i<a;i++)
    		if (belong[i]==1)
    			temp+=data[a][i];
    	belong[a]=2;
    	DFS (a+1,sum+temp);
    }
    
    int main ()
    {
    	while (~scanf("%d",&n))
    	{
    		for (int i=0;i<n;i++)
    			for (int j=0;j<n;j++)   
    				scanf("%d",&data[i][j]);
    		memset(belong,0,sizeof(belong));
    		ans=0;
    		belong[0]=1;
    		DFS(1,0);
    		printf("%d\n",ans);
    	}
    	return 0;
    }

#include <cstdio>
    #include <cstring>
    #define max(a,b) ((a)>(b)?(a):(b))
    
    const int N=30;
    int map[N][N];
    int set[N];    
     
    int main ()
    {
    	int i,j,k,n;
    	scanf("%d", &n);
    	for (i=0;i<n;i++)
    		for (j=0; j<n; j++)
    			scanf("%d", &map[i][j]);
    	// 枚举2^(n-1)个集合，从0开始。没必要枚举2^n个集合，因为集合是互补的
    		int limit=1 << (n-1);
    	int ans=0;
    	for (k=0; k<limit; k++)
    	{
    		int flow = 0;
    		// 将集合k映射到数组set中
    		for (i=0;i<n;i++)  //属于该集合
    			set[i] = (k & (1 << i));
    		for (i=0;i<n;i++)
    		{
    			if (set[i]==0) continue;
    			for (j=0;j<n;j++)
    			{//在同一集合略过
    				if (set[j]) continue;
    				flow += map[i][j];//不在同一集合
    			}
    		}
    		ans=max(ans,flow);
    	}
    	printf("%d\n",ans);
    	return 0;
    }