配对

C++11(clang++ 3.9) 解法, 执行用时: 815ms, 内存消耗: 3532K, 提交时间: 2020-05-24 16:47:49

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=611;
const ll inf=1e16+7;
struct Side{
	int v,ne,w,val;
	Side(){}
	Side(int v,int val):v(v),val(val){}
	bool operator<(const Side &s1)const{
		return val>s1.val;
	}
}S[N*N];
bool vis[N];
int sb,se,sn,a[N],head[N],lu[N],h[N];
ll dis[N],flow[N];
void init(int n){
	sn=0;
	for(int i=0;i<=n;i++) head[i]=-1;
}
void add(int u,int v,int w,int val){
	S[sn].w=w;S[sn].val=val;
	S[sn].v=v;S[sn].ne=head[u];
	head[u]=sn++;
}
void addE(int u,int v,int w,int val){
	add(u,v,w,val);add(v,u,0,-val); 
}
bool dijk(int n){
	priority_queue<Side> q;
	for(int i=0;i<=n;i++){
		lu[i]=-1;	
		dis[i]=flow[i]=inf;
	}
	dis[sb]=0;
	q.push(Side(sb,dis[sb]));
	while(!q.empty()){
		int u=q.top().v,w=q.top().val;q.pop();
		if(dis[u]<w) continue;
		for(int i=head[u];~i;i=S[i].ne){
			int v=S[i].v;
			if(S[i].w>0&&dis[v]>dis[u]+S[i].val+h[u]-h[v]){
				lu[v]=i;
				dis[v]=dis[u]+S[i].val+h[u]-h[v];
				flow[v]=min(flow[u],1ll*S[i].w);
				q.push(Side(v,dis[v]));
			}
		}
	}
	return dis[se]!=inf; 
}
int mfml(int n){
	int ans=0;
	ll ansc=0;
	for(int i=0;i<=n;i++) h[i]=0;
	while(dijk(n)){
		ans+=flow[se];
		ansc+=flow[se]*(dis[se]+h[se]-h[sb]);
		for(int i=lu[se];~i;i=lu[S[i^1].v]){
			S[i].w-=flow[se];
			S[i^1].w+=flow[se];
		}
		for(int i=0;i<=n;i++) h[i]+=dis[i];
	}
	printf("%d %lld\n",ans,-ansc); 
	return 0;
}
int main(){
	int n;
	scanf("%d",&n);
	sb=0;se=n+1;
	init(n+1);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(a[i]&1) addE(sb,i,1,0);
		else addE(i,se,1,0);
		for(int j=1;j<i;j++){
			if((a[i]+a[j])&1){
				if(a[i]&1) addE(i,j,1,-(a[i]^a[j]));
				else addE(j,i,1,-(a[i]^a[j]));
			}
		}
	}
	mfml(n+1);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 4456ms, 内存消耗: 7516K, 提交时间: 2020-05-24 16:42:07

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn=600*600+9,maxv=600*600+9;
struct Edge { int to,cap,cost,nex; };
vector<Edge> G;
int head[maxn],pre[maxn],maxflow=0;
ll mincost=0;
void addedge(int f,int t,int cap,int cost) {
	G.push_back({t,cap,cost,head[f]});
	head[f]=G.size()-1;
	G.push_back({f,0,-cost,head[t]});
	head[t]=G.size()-1;
}
int spfa(int s,int t) {
	queue<int> q;
	static int dis[maxn];
	static bool used[maxn]={};
	memset(dis,0x3f,sizeof(dis));
	memset(pre,0xff,sizeof(pre));
	dis[s]=0;used[s]=1;q.push(s);
	while (!q.empty()) {
		int u=q.front();q.pop();used[u]=0;
		for (int i=head[u];i!=-1;i=G[i].nex) {
			int v=G[i].to;
			if (G[i].cap&&dis[v]>dis[u]+G[i].cost) {
				dis[v]=dis[u]+G[i].cost;
				pre[v]=i;
				if (used[v]==0) q.push(v),used[v]=1;
			}
		}
	}
	return pre[t]!=-1;
}
void MCMF(int s,int t) {
	while (spfa(s,t)) {
		int f=INT_MAX;
		for (int i=pre[t];i!=-1;i=pre[G[i^1].to])
			f=min(f,G[i].cap);
		maxflow+=f;
		for (int i=pre[t];i!=-1;i=pre[G[i^1].to]) {
			G[i].cap-=f;
			G[i^1].cap+=f;
			mincost+=(ll)f*(ll)G[i].cost;
		}
	}
}
vector<int> odd,even;
int a[609]={};
int main() {
	memset(head,-1,sizeof head);
	int n;cin>>n;
	rep(i,1,n+1) {
		scanf("%d",a+i);
		if (a[i]&1) odd.push_back(i);
		else even.push_back(i);
	}
	int s=602,t=603;
	printf("%d ",min(odd.size(),even.size()));
	for (int i:odd) addedge(s,i,1,0);
	for (int i:even) addedge(i,t,1,0);
	for (int i:odd) for (int j:even) addedge(i,j,1,-(a[i]^a[j]));
	MCMF(s,t);
	printf("%lld",-mincost);
}

详情