POJ2531 (Network Saboteur)做题笔记

发表于 | 更新于 | | 阅读次数：

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://poj.org/problem?id=2531
这题需要把所有序号分为两类，直接枚举每一个序号是哪一类就行了，因为N<=20，所以可以直接用一个int类型的每一位来表示每一个序号的类别（某一位是0或1代表其属于对应的类别）。这样直接枚举这个int类型就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

int map[21][21];
int mx=0;
int n;
int main() {
	int tmp=0;
	scanf("%d",&n);
	for (int i=0;i<n;i++) 
		for (int j=0;j<n;j++)
			scanf("%d",&map[i][j]);
	for (int i=1;i<(1<<n)-1;i++) {
		tmp=0;
		for (int j=0;j<n-1;j++)
			for (int k=j+1;k<n;k++) {
				if (((i>>j)&1)^((i>>k)&1)) tmp+=map[j][k];
			}
		mx=std::max(tmp,mx);
	}
	printf("%d",mx);
}