C++14(g++5.4) 解法, 执行用时: 246ms, 内存消耗: 612K, 提交时间: 2020-02-20 18:17:17

#include<bits/stdc++.h>
using namespace std;

int n,t,m;
int f[10000];
int u[10000],v[10000];
int ans;

void dfs(int x)
{
	if(x==n+1){
		int sum=0;
		for(int i=1;i<=m;i++)
		{
			sum+=f[u[i]]^f[v[i]];
		}
		ans=max(ans,sum);
		return ;
	}
	f[x]=1;
	dfs(x+1);
	f[x]=0;
	dfs(x+1);
}

int main()
{
	cin>>t;
	for(int ca=1;ca<=t;ca++)
	{
		ans=0;
		cin>>n>>m;
		for(int i=1,x,y;i<=m;i++) {
			cin>>u[i]>>v[i];
		}
		dfs(1);
		cout<<"Case #"<<ca<<": "<<ans<<"\n";
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 353ms, 内存消耗: 484K, 提交时间: 2023-05-07 13:14:16

#include<bits/stdc++.h>
using namespace std;
int u[300],v[300],n,m,ans;
bool vis[300];
void dfs(int now){
	if(now>n){
		int may=0;
		for(int i=0;i<m;++i)
			if(vis[u[i]]^vis[v[i]])++may;
		ans=max(ans,may);
		return;
	}vis[now]=1;
	dfs(now+1);
	vis[now]=0;
	dfs(now+1);
}
int main(){
	int t;
	scanf("%d",&t);
	for(int k=1;k<=t;++k){
		scanf("%d%d",&n,&m);
		for(int i=0;i<m;++i)scanf("%d%d",u+i,v+i);
		ans=0,dfs(1);
		printf("Case #%d: %d\n",k,ans);
	}
} 

C++(clang++11) 解法, 执行用时: 302ms, 内存消耗: 388K, 提交时间: 2020-12-06 15:51:55

#include<cstdio>

using namespace std;

#define rep(i,a,b) for (int i=(a);i<=(b);i++)

const int N=20,M=N*N;

int T,n,m,ls,ans,maxs,a[N],le[M],ri[M];

int main()
{
	scanf("%d",&T);rep(t,1,T)
	{
		scanf("%d%d",&n,&m);rep(i,1,m) scanf("%d%d",&le[i],&ri[i]);
		maxs=(1<<n)-1;rep(s,0,maxs)
		{
			rep(i,1,n) a[i]=(s>>i-1)&1;
			ls=0;rep(i,1,m) if (a[le[i]]!=a[ri[i]]) ls++;
			if (ls>ans) ans=ls;
		}
		printf("Case #%d: %d\n",t,ans);ans=0;
	}
	return 0;
}