hackerrank 训练军队

在神奇的Kasukabe国家，人们努力拥有一个技能。一共有N个类型的技能，并且开始的时候拥有第 i 种技能的人有Ci个。

这个国家有T个巫师，他们有能力将一个人的技能进行转换。每个巫师有两个转移的列表，A和B , 他可以将一个人的技能从技能x转换为技能y当且仅当x∈A并且y∈B，转换后他会把x从A中删除，y从B中删除。

注意：

一个巫师可以进行 0 或多次转换，只要他的转换满足上述要求。
一个人可以进行多次转换。
技能同类转换也是允许的。

你的目标是设计一系列的转换是的最后所有人获得最多不同的技能。

只要想到网络流就很容易了

#include<cstdio>

#include<algorithm>

#define MN 40001

using namespace std;

int read_p,read_ca,read_f;

inline int read(){

    read_p=;read_ca=getchar();read_f=;

    while(read_ca<''||read_ca>'') read_f=read_ca=='-'?-:read_f,read_ca=getchar();

    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p*read_f;

}

const int INF=1e9;

struct na{int y,z,ne;}b[MN*];

int n,m,num=,no=,S,T,mmh=,g[MN],c[MN],d[MN],l[MN];

inline void in(int x,int y,int z){b[++num].y=y;b[num].z=z;b[num].ne=l[x];l[x]=num;}

inline void add(int x,int y,int z,int Z=){in(x,y,z);in(y,x,Z);}

inline int min(int a,int b){return a<b?a:b;}

int sap(int x,int f){

    if (x==T) return f;

    int h=,q;

    for (int i=d[x];i;i=b[i].ne)

    if (b[i].z&&g[b[i].y]+==g[x]){

        q=sap(b[i].y,min(b[i].z,f-h));

        h+=q;b[i].z-=q;b[i^].z+=q;

        if (h==f||g[S]==no) return h;

    }

    if (!(--c[g[x]])) g[S]=no;d[x]=l[x];c[++g[x]]++;

    return h;

}

signed main(){

    static int a[],b[];

    register int i,j;

    n=read();m=read();S=;T=no=n*m*+n+;

    if (!m){

        for (int i=;i<=n;i++) mmh+=bool(read());

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

        return ;

    }

    for (i=;i<=n;i++) add(S,i,read()),add(n*m*+i,T,);

    for (int k=;k<m;k++){

        int N=k**n;

        a[]=read();

        for (i=;i<=a[];i++) a[i]=read();

        b[]=read();

        for (i=;i<=b[];i++) b[i]=read();

        for (i=;i<=n;i++) add(N+i,N+n+i,),add(N+*n+i,N+*n+i,),add(N+i,N+*n+i,INF);

        for (i=;i<=a[];i++)

        for (j=;j<=b[];j++) add(N+n+a[i],N+*n+b[j],);

    }

    for (;g[S]<no;mmh+=sap(S,INF));

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

}

秒客网

hackerrank 训练军队

相关文章