搜索
查看: 207|回复: 2

求助求助

[复制链接]
 楼主| 发表于 2019-1-27 19:19:54 | 显示全部楼层 |阅读模式
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
发表于 2019-1-27 19:20:46 | 显示全部楼层
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,e[2009][2009],flag=0,top,s[100009],ans,book[100009];
void dfs(int u)
{
    if(u==n)
    {
        top++;
        s[top]=n;
        int minx=2147483647;
        for(int i=1;i<top;i++)
        {
            if(e[s[i]][s[i+1]]<minx)
            {
                minx=e[s[i]][s[i+1]];
            }
        }
        ans+=minx;
        for(int i=1;i<top;i++)
        {
            e[s[i]][s[i+1]]-=minx;
            e[s[i+1]][s[i]]+=minx;
        }
        flag=1;
        return;
    }
    if(book[u]==1)
    {
        return;
    }
    book[u]=1;
    top++;
    s[top]=u;
     
    for(int i=0;i<=n;i++)
    {
        if(e[u][i]>0)
        {
            dfs(i);
        }
    }
    top--;
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    n++;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        e[a][b]+=1;
        e[b][n]=1;
        e[0][a]=1;
    }
    while(1>0)
    {
        memset(book,0,sizeof(book));
        flag=0;
        top=0;
        dfs(0);
        if(flag==0)
        {
            break;
        }
    }
    printf("%d",ans);
    return 0;
}
发表于 2019-1-29 09:42:26 | 显示全部楼层
额您看过啊哈算法吗?没看过建议看一下
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

广播台
特别关注
快速回复 返回顶部 返回列表