[LUOGU]P3701 主席树（假的）

有人恶意刷难度。。。就一个最大流模板。。。

但是题面吼啊2333
#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

int n,m;

const int N=505,S=0,T=504;

char s1[105][10],s2[105][10],ct1,ct2;

int cnt[5],lif1[105],lif2[105];

int h[N<<1],ecnt=1,head[N<<1];

struct Edge {

    int nxt,to,val;

} e[500*500];

void add(int bg,int ed,int val) {

    e[++ecnt].nxt=head[bg];

    e[ecnt].to=ed;

    e[ecnt].val=val;

    head[bg]=ecnt;

}

void ins(int x,int y,int flow) {

	add(x,y,flow);

	add(y,x,0);

}

bool bfs() {

    memset(h,-1,sizeof h);

    queue<int>q;

    q.push(S);

    h[S]=0;

    while(!q.empty()) {

        int u=q.front();

        q.pop();

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

            int v=e[i].to;

            if(h[v]==-1&&e[i].val) {

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

                q.push(v);

            }

        }

    }

    return h[T]!=-1;

}

int dfs(int x,int f) {

    if(x==T)return f;

    int used=0,tp;

    for(int i=head[x]; i; i=e[i].nxt) {

        int v=e[i].to;

        if(h[v]-1==h[x]&&e[i].val) {

            tp=dfs(v,min(e[i].val,f-used));

            used+=tp;

            e[i].val-=tp;

            e[i^1].val+=tp;

            if(used==f)return f;

        }

    }

    if(used==0)h[x]=-1;

    return used;

}

int maxflow;

void dinic() {

    maxflow=0;

    while(bfs()) {

        maxflow+=dfs(0,0x3f3f3f3f);

    }

}

int main() {

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%s",s1[i]),ct1+=s1[i][0]=='Y'?1:0;

	for(int i=1;i<=n;i++)

		scanf("%s",s2[i]),ct2+=s2[i][0]=='Y'?1:0;

	for(int i=1;i<=n;i++)

		scanf("%d",&lif1[i]),lif1[i]+=s1[i][0]=='J'?ct1:0;

	for(int i=1;i<=n;i++)

		scanf("%d",&lif2[i]),lif2[i]+=s2[i][0]=='J'?ct2:0;;

	for(int i=1;i<=n;i++) {ins(S,i,lif1[i]);ins(i+n,T,lif2[i]);}

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

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

			if(s1[i][0]=='J'&&(s2[j][0]=='W'||s2[j][0]=='H')) ins(i,j+n,1);

			if(s1[i][0]=='E'&&(s2[j][0]=='J'||s2[j][0]=='Y')) ins(i,j+n,1);

			if(s1[i][0]=='Y'&&(s2[j][0]=='H'||s2[j][0]=='J')) ins(i,j+n,1);

			if(s1[i][0]=='H'&&(s2[j][0]=='W'||s2[j][0]=='E')) ins(i,j+n,1);

			if(s1[i][0]=='W'&&(s2[j][0]=='Y'||s2[j][0]=='E')) ins(i,j+n,1);

		}

	}

	dinic();

	cout<<min(maxflow,m);

}
巴特西

[LUOGU]P3701 主席树（假的）

最新文章

热门文章
