321B

MCMF必须是满足流量最大为前提下的最小费用流(这里是最大费用流)

因此还必须不断地枚举m的流量才行

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int maxn = 1e5+11;

const int oo = 0x3f3f3f3f;

int to[maxn<<1],cost[maxn<<1],cap[maxn<<1],flow[maxn<<1],nxt[maxn<<1];

int head[maxn],tot;

void init(){

    memset(head,-1,sizeof head);

    tot=0;

}

void add(int u,int v,int c,int w){

    to[tot]=v;

    cap[tot]=c;

    flow[tot]=0;

    cost[tot]=w;

    nxt[tot]=head[u];

    head[u]=tot++;

    swap(u,v);

    to[tot]=v;

    cap[tot]=0;

    flow[tot]=0;

    cost[tot]=-w;

    nxt[tot]=head[u];

    head[u]=tot++;

}

struct QUEUE{

    int que[maxn];

    int front,rear;

    void init(){front=rear=0;}

    void push(int x){que[rear++]=x;}

    int pop(){return que[front++];}

    bool empty(){return front==rear;}

}que;

int n,m,s,t;

int dis[maxn],pre[maxn];

bool vis[maxn];

bool spfa(){

	que.init();

	memset(dis,0x80,sizeof dis);

	memset(vis,0,sizeof vis);

	memset(pre,-1,sizeof pre);

	que.push(s);dis[s]=0;vis[s]=1;

	while(!que.empty()){

		int u = que.pop();

		vis[u]=0;

		for(int i = head[u]; ~i; i = nxt[i]){

			int v=to[i],c=cap[i],f=flow[i],w=cost[i];

			if(c>f&&dis[v]<dis[u]+w){

				dis[v]=dis[u]+w;

				pre[v]=i;

				if(!vis[v]){

					vis[v]=1;

					que.push(v);

				}

			}

		}

	}

	if(pre[t]==-1)return 0;

	return 1;

}

int mcmf(){

	int mc=0,mf=0;

	while(spfa()){

		int mn=oo;

		for(int i = pre[t]; ~i; i = pre[to[i^1]]){

			mn=min(mn,cap[i]-flow[i]);

		}

		for(int i = pre[t]; ~i; i = pre[to[i^1]]){

			flow[i]+=mn;

			flow[i^1]-=mn;

			mc+=cost[i]*mn;

		}

		mf+=mn;

	}

	return mc;

}

int n1,n2,n3,a[maxn],b[maxn],atr[maxn],x;

char str[199];

int main(){

	while(scanf("%d%d",&n1,&n2)!=EOF){

		init();

		if(n1<n2){

			n3=n2-n1;

			n=2*n2+2;

			t=n;s=t-1;

		}

		else{

			n3=0;

			n=n1+n2+2;

			t=n;s=n-1;

		}

		for(int i = 1; i <= n1; i++){

			scanf("%s%d",str,&a[i]);

			if(str[0]=='A') atr[i]=1;

			else atr[i]=0;

		}

		for(int i = 1; i <= n2; i++){

			scanf("%d",&b[i]);

		}

		if(n3) for(int i = 1; i <= n3; i++){

			atr[i+n1]=1;

			a[i+n1]=0;

		}

		for(int i = 1; i <= n2; i++){

			add(s,i,1,0);

		}

		for(int i = 1; i <= n1+n3; i++){

			add(i+n2,t,1,0);

		}

		for(int i = 1; i <= n2; i++){

			for(int j = 1; j <= n1+n3; j++){

				if(atr[j]==1){

					if(b[i]>=a[j]){

						if(a[j]!=-oo) add(i,j+n2,1,b[i]-a[j]);

						else add(i,j+n2,1,b[i]);

					}

					else add(i,j+n2,1,-9999);

				}

				else{

					if(b[i]>a[j]){

						add(i,j+n2,1,0);

					}

					else add(i,j+n2,1,-9999);

				}

			}

		}

		printf("%d\n",mcmf());

	}

    return 0;

}

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define INF 0x3f3f3f3f3f3f3f3fLL

#define mod 1000000007

#define pb push_back

#define sq(x) ((x)*(x))

#define sz(a) ((int)a.size())

#define x first

#define y second

#define eps 1e-8

#define bpt(x) (__builtin_popcount(x))

#define bptl(x) (__builtin_popcountll(x))

#define bit(x, y) (((x)>>(y))&1)

#define bclz(x) (__builtin_clz(x))

#define bclzl(x) (__builtin_clzll(x))

#define bctz(x) (__builtin_ctz(x))

#define bctzl(x) (__builtin_ctzll(x))

#define rands(n) (rand()%n+1)

#define rand0(n) (rands(n)-1)

#define Rands(n) ((INT)rand()*rand()%n+1)

#define Rand0(n) (Rands(n)-1)

#define PQ priority_queue<pii, vector<pii>, greater<pii> >

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

using namespace std;

typedef long long INT;

typedef vector<int> VI;

typedef pair<int, int> pii;

typedef pair<INT, INT> PII;

typedef pair<pii, int> ppi;

typedef double DO;

template<typename T, typename U> inline void smin(T &a, U b) {if (a>b) a=b;}

template<typename T, typename U> inline void smax(T &a, U b) {if (a<b) a=b;}

template<class T>inline void gn(T &x) {char c, sg=0; while (c=getchar(), (c>'9' || c<'0') && c!='-');for((c=='-'?sg=1, c=getchar():0), x=0; c>='0' && c<='9'; c=getchar()) x=(x<<1)+(x<<3)+c-'0';if (sg) x=-x;}

template<class T>inline void print(T x) {if (x<0) {putchar('-');return print(-x);}if (x<10) {putchar('0'+x);return;} print(x/10);putchar(x%10+'0');}

int power(int a, int b, int m, int ans=1) {

	for (; b; b>>=1, a=1LL*a*a%m) if (b&1) ans=1LL*ans*a%m;

	return ans;

}

#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)

    #define lld "%I64d"

#else

    #define lld "%lld"

#endif

#define NN 400

#define MC 100000

int N, M, a[NN], b[NN], V, src, tar, mx, S, T;

int adj[NN][NN], cap[NN][NN], cost[NN][NN];

int dis[NN], q[NN*NN], qf, qb, pre[NN], C, deg[NN];

char s[NN][10];

void init() {

	memset(pre, -1, sizeof(pre));

	memset(deg, 0, sizeof(deg));

}

void add_edge(int u, int v, int w, int c) {

	adj[u][deg[u]++]=v;

	adj[v][deg[v]++]=u;

	cap[u][v]=w; cap[v][u]=0;

	cost[u][v]=c; cost[v][u]=-c;

}

int Mincost_Maxflow() {

	int ans=0, bot; C=0;

	while(1) {

		memset(dis, 0x3f, sizeof(dis));

		qf=qb=0;

		dis[src]=0; q[qb++]=src;

		while(qf<qb) {

			int u=q[qf++];

			for(int i=0; i<deg[u]; i++) {

				int v=adj[u][i];

				if(cap[u][v]==0) continue;

				if(dis[v]>dis[u]+cost[u][v]) {

					dis[v]=dis[u]+cost[u][v];

					q[qb++]=v;

					pre[v]=u;

				}

			}

		}

		if(dis[tar]>=inf) return ans;

		bot=inf;

		for(int u=tar; u!=src; u=pre[u]) bot=min(bot, cap[pre[u]][u]);

		ans+=bot;

		for(int u=tar; u!=src; u=pre[u]){

			cap[pre[u]][u]-=bot;

			cap[u][pre[u]]+=bot;

		}

		C+=dis[tar]*bot;

	}

	return ans;

}

int main() {

	gn(N); gn(M);

	for(int i=1; i<=N; i++) {

		scanf("%s", s[i]);  gn(a[i]);

	}

	for(int i=1; i<=M; i++)  gn(b[i]);

	src=0; tar=M+N+1; S=M+N+2; T=M+N+3;

	for(int k=1; k<=M; k++) {

		init();

		add_edge(src, S, k, 0);

		for(int i=1; i<=M; i++) {

			add_edge(S, i, 1, 0);

			add_edge(i, T, 1, -b[i]);

			for(int j=1; j<=N; j++) {

				if(b[i]>=a[j] && s[j][0]=='A') add_edge(i, j+M, 1, a[j]-b[i]);

				else if(b[i]>a[j] && s[j][0]=='D') add_edge(i, j+M, 1, 0);

			}

		}

		for(int i=1; i<=N; i++) add_edge(M+i, tar, 1, 0);

		add_edge(T, tar, M, MC);

		Mincost_Maxflow();

		if(cap[tar][T]>max(0, k-N)) continue;

		mx= max(mx, -C+cap[tar][T]*MC);

	}

	printf("%d\n", mx);

	return 0;

}

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<queue>

typedef long long ll;

using namespace std;

const int maxn = 7e4+11;

const int oo = 0x3f3f3f3f;

int to[maxn<<1],cost[maxn<<1],cap[maxn<<1],flow[maxn<<1],nxt[maxn<<1];

int _to[maxn<<1],_cost[maxn<<1],_cap[maxn<<1],_flow[maxn<<1],_nxt[maxn<<2];

int head[maxn],tot;

int _head[maxn],_tot;

void init(){

    memset(head,-1,sizeof head);

    tot=0;

}

void add(int u,int v,int c,int w){

    to[tot]=v;

    cap[tot]=c;

    flow[tot]=0;

    cost[tot]=w;

    nxt[tot]=head[u];

    head[u]=tot++;

    swap(u,v);

    to[tot]=v;

    cap[tot]=0;

    flow[tot]=0;

    cost[tot]=-w;

    nxt[tot]=head[u];

    head[u]=tot++;

}

struct QUEUE{

    int que[maxn];

    int front,rear;

    void init(){front=rear=0;}

    void push(int x){que[rear++]=x;}

    int pop(){return que[front++];}

    bool empty(){return front==rear;}

}que;

int n,m,s,t;

int dis[maxn],pre[maxn];

bool vis[maxn];

bool spfa(){

	que.init();

	memset(dis,oo,sizeof dis);

	memset(vis,0,sizeof vis);

	memset(pre,-1,sizeof pre);

	que.push(s);dis[s]=0;vis[s]=1;

	while(!que.empty()){

		int u = que.pop();

		vis[u]=0;

		for(int i = head[u]; ~i; i = nxt[i]){

			int v=to[i],c=cap[i],f=flow[i],w=cost[i];

			if(c>f&&dis[v]>dis[u]+w){

				dis[v]=dis[u]+w;

				pre[v]=i;

				if(!vis[v]){

					vis[v]=1;

					que.push(v);

				}

			}

		}

	}

	if(pre[t]==-1)return 0;

	return 1;

}

ll mcmf(){

	ll mc=0,mf=0;

	while(spfa()){

		int mn=oo;

		for(int i = pre[t]; ~i; i = pre[to[i^1]]){

			mn=min(mn,cap[i]-flow[i]);

		}

		for(int i = pre[t]; ~i; i = pre[to[i^1]]){

			flow[i]+=mn;

			flow[i^1]-=mn;

			mc+=1ll*cost[i]*mn;

		}

		mf+=mn;

	}

	return mc;

}

void backup(){

	memcpy(_to,to,sizeof to);

	memcpy(_nxt,nxt,sizeof nxt);

	memcpy(_cap,cap,sizeof cap);

	memcpy(_flow,flow,sizeof flow);

	memcpy(_cost,cost,sizeof cost);

	memcpy(_head,head,sizeof head);

	_tot=tot;

}

void recover(){

	memcpy(to,_to,sizeof to);

	memcpy(nxt,_nxt,sizeof nxt);

	memcpy(cap,_cap,sizeof cap);

	memcpy(flow,_flow,sizeof flow);

	memcpy(cost,_cost,sizeof cost);

	memcpy(head,_head,sizeof head);

	tot=_tot;

}

int n1,n2,n3,a[maxn],b[maxn],atr[maxn],x;

char str[199];

int main(){

	while(scanf("%d%d",&n1,&n2)!=EOF){

		init();int ss,tt;ll maxcost=oo;

		for(int i = 1; i <= n1; i++){

			scanf("%s%d",str,&a[i]);

			if(str[0]=='A') atr[i]=1;

			else atr[i]=0;

		}

		for(int i = 1; i <= n2; i++){

			scanf("%d",&b[i]);

		}

		n=n1+2*n2+4;t=n;s=t-1;tt=s-1;ss=tt-1;

		int guaidian=n2,duimian=n1+n2;

		ll bigInt=200000;

		for(int i = 1; i <= n2; i++) add(ss,i,1,0);

		for(int i = 1; i <= n1; i++) add(i+duimian,tt,1,0);

		for(int i = 1; i <= n2; i++){

			add(i,i+guaidian,1,bigInt);

			add(i+guaidian,tt,1,-b[i]);

			for(int j = 1; j <= n1; j++){

				if(atr[j]==1) if(b[i]>=a[j])add(i,j+duimian,1,-(b[i]-a[j]));

				if(atr[j]==0) if(b[i]>a[j])add(i,j+duimian,1,0);

			}

		}

		backup();

		for(int k = 1; k <= n2; k++){

//			if(k>1)break;

			recover();

			add(s,ss,k,0);

			add(tt,t,k,0);

			if(k<=n1) maxcost=min(maxcost,mcmf());

			else maxcost=min(maxcost,mcmf()+(k-n1)*bigInt);

		}

		maxcost=-maxcost;

		printf("%lld\n",maxcost);

	}

	return 0;

	return 0;

}

510E

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<queue>

#include<vector>

#include<set>

using namespace std;

const int maxn = 1e5+11;

const int oo = 0x3f3f3f3f;

int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1];

int head[maxn],tot;

struct UF{

	int p[256];

	void init(){

		for(int i = 0; i < 256; i++) p[i]=i;

	}

	int find(int x){

		return p[x]==x?x:p[x]=find(p[x]);

	}

	void link(int a,int b){

		a=find(a);b=find(b);

		if(a!=b) p[a]=b;

	}

}uf;

void init(){

    memset(head,-1,sizeof head);

    tot=0;

}

void add(int u,int v,int w){

    to[tot]=v;

    nxt[tot]=head[u];

    cap[tot]=w;

    flow[tot]=0;

    head[u]=tot++;

    swap(u,v);

    to[tot]=v;

    nxt[tot]=head[u];

    cap[tot]=0;

    flow[tot]=0;

    head[u]=tot++;

}

//int n,m,s,t;

//int dis[maxn],pre[maxn],cur[maxn],gap[maxn];

//bool vis[maxn];

struct QUEUE{

    int que[maxn];

    int front,rear;

    void init(){front=rear=0;}

    void push(int u){que[rear++]=u;}

    int pop(){return que[front++];}

    bool empty(){return front==rear;}

}que;

int n,m,s,t;

int gap[maxn],dep[maxn];

void bfs(){

	memset(dep,-1,sizeof dep);

	memset(gap,0,sizeof gap);

	gap[0]=1;

	que.init();

	que.push(t);dep[t]=0;

	while(!que.empty()){

		int u = que.pop();

		for(int i = head[u]; ~i; i = nxt[i]){

			int v=to[i];

			if(~dep[v])continue;

			que.push(v);

			dep[v]=dep[u]+1;

			gap[dep[v]]++;

		}

	}

}

int cur[maxn],S[maxn];

int isap(){

	bfs();

	memcpy(cur,head,sizeof head);

	int ans=0,top=0,u=s;

	while(dep[s]<n){

		if(u==t){

			int mn=oo;

			int inser;

			for(int i = 0; i < top; i++){

				if(mn>cap[S[i]]-flow[S[i]]){

					mn=cap[S[i]]-flow[S[i]];

					inser=i;

				}

			}

			for(int i = 0; i < top; i++){

				flow[S[i]]+=mn;

				flow[S[i]^1]-=mn;

			}

			ans+=mn;

			top=inser;

			u=to[S[top]^1];

			continue;

		}

		bool flag=0;

		int v;

		for(int i = cur[u]; ~i; i = nxt[i]){

			v=to[i];

			if(cap[i]-flow[i]&&dep[v]+1==dep[u]){

				flag=1;

				cur[u]=i;

				break;

			}

		}

		if(flag){

			S[top++]=cur[u];

			u=v;

			continue;

		}

		int mn=n;

		for(int i = head[u]; ~i; i = nxt[i]){

			if(cap[i]-flow[i]&&dep[to[i]]<mn){

				mn=dep[to[i]];

				cur[u]=i;

			}

		}

		gap[dep[u]]--;

		if(!gap[dep[u]])return ans;

		dep[u]=mn+1;

		gap[dep[u]]++;

		if(u!=s)u=to[S[--top]^1];

	}

	return ans;

}

bool isnprime[maxn];

void sai(){

	isnprime[0]=isnprime[1]=1;

	for(int i = 2; i*i < 100000; i++){

		if(!isnprime[i]){

			for(int j = 2*i; j < 100000; j+=i){

				isnprime[j]=1;

			}

		}

	}

}

bool go[maxn];

vector<int> G[maxn];

int cnt;

vector<int> biao[500];

vector<int> biao2[500];

int biao3[maxn];

vector<int> biao4[maxn];

//void dfs(int u,int k){

//	go[u]=1;GG[k].push_back(u);

//	for(int i = 0; i < G[u].size(); i++){

//		if(!go[G[u][i]]) dfs(G[u][i],k);

//	}

//}

int n1,a[maxn];

bool in[maxn];

bool dfs(int now,int cur,int p,int one){

	if(cur==biao[now].size()+1){return 1;}

	if(cur==1){

		for(int i = 0; i < biao[now].size(); i++){

			in[biao[now][i]]=1; biao3[cur]=biao[now][i];

			bool flag=dfs(now,cur+1,biao[now][i],biao[now][i]);

			if(flag)return 1;

			in[biao[now][i]]=0;

		}

	}

	else{

		int qian=p;

		for(int i = 0; i < biao2[qian].size(); i++){

			if(cur!=biao[now].size()) {

				if(!isnprime[a[biao2[qian][i]]+a[one]])if(!isnprime[a[qian]+a[biao2[qian][i]]] && !in[biao2[qian][i]]){

					in[biao2[qian][i]]=1; biao3[cur]=biao2[qian][i];

					bool flag=dfs(now,cur+1,biao2[qian][i],one);

					if(flag)return 1;

					in[biao2[qian][i]]=0;

				}

			}

			else{

				if(!isnprime[a[qian]+a[biao2[qian][i]]] && !in[biao2[qian][i]]){

					in[biao2[qian][i]]=1; biao3[cur]=biao2[qian][i];

					bool flag=dfs(now,cur+1,biao2[qian][i],one);

					if(flag)return 1;

					in[biao2[qian][i]]=0;

				}

			}

		}

	}

}

int main(){

	sai();

	while(scanf("%d",&n1)!=EOF){

		init();

		for(int i = 1; i <= n1; i++){

			scanf("%d",&a[i]);

		}

		n=n1+2;s=n-1;t=n;

		for(int i = 1; i <= n1; i++){

			if(a[i]&1) add(s,i,2);

			else add(i,t,2);

		}

		for(int i = 1; i <= n1; i++){

			if(a[i]&1) for(int j = 1; j <= n1; j++){

				if(!(a[j]&1)) if(!isnprime[a[i]+a[j]]) add(i,j,1);

			}

		}

		int ans=isap();

		if(ans!=n1){

			printf("Impossible\n");

			continue;

		}

		memset(G,0,sizeof G);

		for(int i = 1; i <= n1; i++){

			for(int j = head[i]; ~j; j = nxt[j]){

				int v=to[j],c=cap[j],f=flow[j];

				if(c==0||v==s||v==t) continue;

				if(f==1)G[i].push_back(v);

			}

		}

//		for(int i = 1; i <= n1; i++){

//			cout<<i<<": ";

//			if(G[i].size()==0) cout<<endl;

//			for(int j = 0; j < G[i].size(); j++){

//				if(j==G[i].size()-1) printf("%d\n",G[i][j]);

//				else printf("%d ",G[i][j]);

//			}

//		}

		uf.init();

		for(int i = 1; i <= n1; i++){

			for(int j = 0; j < G[i].size(); j++){

				uf.link(i,G[i][j]);

			}

		}

		for(int i = 1; i <= n1; i++) uf.find(i);

		cnt=0;

		memset(biao,0,sizeof biao);

		for(int i = 1; i <= n1; i++){

			if(uf.p[i]==i){

				cnt++;

			}

			biao[uf.p[i]].push_back(i);

		}

		printf("%d\n",cnt);

		int cnt2=0;

		memset(biao4,0,sizeof biao4);

		for(int i = 1; i <= n1; i++){

			if(biao[i].size()) printf("%d ",biao[i].size()),cnt2++;

			for(int j = 0; j < biao[i].size(); j++){

				biao4[cnt2].push_back(biao[i][j]);

//				if(j==biao[i].size()-1) printf("%d\n",biao[i][j]);

//				else printf("%d ",biao[i][j]);

			}

		}

		memcpy(biao,biao4,sizeof biao);

//		cout<<cnt2-cnt<<"ewe"<<endl;

		for(int i = 1; i <= cnt; i++){

			memset(biao2,0,sizeof biao2);

			for(int j = 0; j < biao[i].size(); j++){

				for(int k = 0; k < biao[i].size(); k++){

					if(j!=k) if(!isnprime[a[biao[i][j]]+a[biao[i][k]]]) biao2[biao[i][j]].push_back(biao[i][k]),cout<<a[biao[i][j]]<<" "<<a[biao[i][k]]<<endl;

				}

			}

			memset(biao3,0,sizeof biao3); memset(in,0,sizeof in);

			dfs(i,1,0,666);

			for(int j = 1; j <= biao[i].size(); j++){

				if(j==biao[i].size()) printf("%d\n",biao3[j]);

				else printf("%d ",biao3[j]);

			}

		}

	}

	return 0;

}