poj1087&&hdu1526 最大流

多源多汇。

比较明显的建图。对于电器，可以从源点与各个电器相连，容量为1，表示这个电器有1个，然后对于各种接头，那可以各个接头与汇点相连，容量为1，表示每个接头只能用一次。

然后对于能够相互转换的接头，其容量为无穷，文中写到转换器可以无穷使用。然后对于电器和其使用的接头，相连，容量为1表示该电器使用该接头。然后求一次最大流，表示最多可以使用的电器，然后见一下即可。

由于字符串，用map搞了半天。

poj 79MS

hdu 15MS

下面是poj代码:

#include<stdio.h>

#include<string.h>

#include<string>

#include<map>

#include<queue>

#include<iostream>

#define maxn 500

#define INF 9999999

using namespace std;

map<string,int>d,num;

int mp[maxn][maxn],n,m,fn,vis[maxn],F;//fn表示插头的种类数

string name,s1,s2;

string s[],fname[];

int min(int x,int y)

{return x<y?x:y;}

void makemap()

{

    int i,j;

    for(i=;i<m;i++)

    {

        mp[d[s[i]]][d[fname[i]]]=;

        //printf("%d %d\n",d[s[i]],d[fname[i]]);

    }

    for(i=;i<=F;i++)

    {

        mp[i][n+]=;

    }

    for(i=fn+;i<=n;i++)

    {

        mp[][i]=;

    }

}

int BFS()

{

    int i,j;

    queue<int>q;

    memset(vis,-,sizeof(vis));

    vis[]=;

    q.push();

    while(!q.empty())

    {

        int t=q.front();

        q.pop();

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

        {

            if(vis[i]<&&mp[t][i])

            {

                vis[i]=vis[t]+;

                q.push(i);

            }

        }

    }

    if(vis[n+]>)

        return ;

    return ;

}

int dfs(int u,int low)

{

    int i,j,a;

    if(n+==u)

        return low;

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

    {

        if(vis[i]==vis[u]+&&mp[u][i])

        {

            a=dfs(i,min(low,mp[u][i]));

            if(!a)continue;

            mp[u][i]-=a;

            mp[i][u]+=a;

            return a;

        }

    }

    return ;

}

int main()

{

    int t,i,j,cou=;

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

    {

        memset(mp,,sizeof(mp));

        for(i=;i<F;i++)

        {

            cin>>name;

            d[name]=cou++;

        }

        scanf("%d",&m);

        for(i=;i<m;i++)

        {

            cin>>s[i];

            cin>>fname[i];

            if(!d[fname[i]])

                d[fname[i]]=cou++;

        }

        fn=cou-;

        //printf("%d\n",fn);

        for(i=;i<m;i++)

        {

            if(!d[s[i]])

                d[s[i]]=cou++;

        }

        n=cou-;

        makemap();

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

        scanf("%d",&t);

        for(i=;i<t;i++)

        {

            cin>>s1>>s2;

            mp[d[s1]][d[s2]]=INF;

        }

        //printf("%d\n",d[s[0]]);

        /*for(i=0;i<=n+1;i++)

        {

            for(j=0;j<=n+1;j++)

            {

                printf("%d ",mp[i][j]);

            }

            printf("\n");

        }*/

        int ans=;

        while(BFS())

        {

            while()

            {

                int a=dfs(,INF);

                if(!a)break;

                ans+=a;

            }

        }

        printf("%d\n",m-ans);

    }

}

hdu比较坑，爆栈，然后加了一句话#pragma comment(linker, "/STACK:1024000000,1024000000")

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<stdio.h>

#include<string.h>

#include<string>

#include<map>

#include<queue>

#include<iostream>

#define maxn 500

#define INF 9999999

using namespace std;

map<string,int>d,num;

int mp[maxn][maxn],n,m,fn,vis[maxn],F;//fn表示插头的种类数

string name,s1,s2;

string s[],fname[];

int min(int x,int y)

{return x<y?x:y;}

void makemap()

{

    int i,j;

    for(i=;i<m;i++)

    {

        mp[d[s[i]]][d[fname[i]]]=;

        //printf("%d %d\n",d[s[i]],d[fname[i]]);

    }

    for(i=;i<=F;i++)

    {

        mp[i][n+]=;

    }

    for(i=fn+;i<=n;i++)

    {

        mp[][i]=;

    }

}

int BFS()

{

    int i,j;

    queue<int>q;

    memset(vis,-,sizeof(vis));

    vis[]=;

    q.push();

    while(!q.empty())

    {

        int t=q.front();

        q.pop();

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

        {

            if(vis[i]<&&mp[t][i])

            {

                vis[i]=vis[t]+;

                q.push(i);

            }

        }

    }

    if(vis[n+]>)

        return ;

    return ;

}

int dfs(int u,int low)

{

    int i,j,a;

    if(n+==u)

        return low;

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

    {

        if(vis[i]==vis[u]+&&mp[u][i])

        {

            a=dfs(i,min(low,mp[u][i]));

            if(!a)continue;

            mp[u][i]-=a;

            mp[i][u]+=a;

            return a;

        }

    }

    return ;

}

int main()

{

    int t,i,j,cou,ft;

    scanf("%d",&ft);

    while(ft--)

    {

        cou=;

        scanf("%d",&F);

        memset(mp,,sizeof(mp));

        d.clear();

        for(i=;i<F;i++)

        {

            cin>>name;

            d[name]=cou++;

        }

        scanf("%d",&m);

        for(i=;i<m;i++)

        {

            cin>>s[i];

            cin>>fname[i];

            if(!d[fname[i]])

                d[fname[i]]=cou++;

        }

        fn=cou-;

        //printf("%d\n",fn);

        for(i=;i<m;i++)

        {

            if(!d[s[i]])

                d[s[i]]=cou++;

        }

        n=cou-;

        makemap();

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

        scanf("%d",&t);

        for(i=;i<t;i++)

        {

            cin>>s1>>s2;

            mp[d[s1]][d[s2]]=INF;

        }

        //printf("%d\n",d[s[0]]);

        /*for(i=0;i<=n+1;i++)

        {

            for(j=0;j<=n+1;j++)

            {

                printf("%d ",mp[i][j]);

            }

            printf("\n");

        }*/

        int ans=;

        while(BFS())

        {

            while()

            {

                int a=dfs(,INF);

                if(!a)break;

                ans+=a;

            }

        }

        printf("%d\n",m-ans);

        if(ft)printf("\n");

    }

}

巴特西

poj1087&&hdu1526 最大流

最新文章

热门文章