#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,T;
vector<int> f;
vector<int> pre;
vector<vector<int> > c;
deque<int> q;

int bfs_1(int s,int t)
{
    f.resize(0);
    f.resize(c.size(),0);
    f[s]=oo_max;
    pre.resize(0);
    pre.resize(c.size(),-1);
    pre[s]=s;
    q.resize(0);
    for (q.push_back(s);(!q.empty())&&pre[t]==-1;q.pop_front())
    {
        int now=q.front();
        for (int i=0;i<c.size();i++)
            if (c[now][i]&&pre[i]==-1)
            {
                pre[i]=now;
                f[i]=min(c[now][i],f[now]);
                q.push_back(i);
            }
    }
    return ((pre[t]!=-1)?f[t]:-1);
}

int max_flow_1(int s,int t)
{
    int temp=0,ans=0;
    while ((temp=bfs_1(s,t))!=-1)
    {
        for (int i=t;i!=s;i=pre[i])
            c[pre[i]][i]-=temp,c[i][pre[i]]+=temp;
        ans+=temp;
    }
    return ans;
}

int main()
{
    while (~scanf("%d",&T))
        for (int t=1;t<=T;t++)
        {
            scanf("%d%d",&n,&m);
            c.resize(0);
            c.resize(2*(n+1));
            for (int i=0;i<c.size();i++)
                c[i].resize(c.size(),0);
            for (int i=1;i<n;i++)
                scanf("%d",&c[n+1+i][i]);
            for (int i=1;i<=m;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                c[x][n+1+y]=c[y][n+1+x]=oo_max;
            }
            c[2*n+1][n]=oo_max;
            int ans=max_flow_1(0,n);
            if (ans==0)
                printf("Min!\n");
            else if (ans>=oo_max)
                printf("Max!\n");
            else
                printf("%d\n",ans);
        }
}

无向图最小割点集数量求法：原图中若点ab有边，则新建点a'->b,b'->a，边权00.对于每一个点i，i->i'，边权为点权（点为0或n则为00）求新图最小割。

有向图最小割点集数量求法：原图中若点a到b有边，则新建点a'->b，边权00.对于每一个点i，i->i'，边权为点权（点为0或n则为00）求新图最小割。

niujinyu的答案哦

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,T;
vector<int> f;
vector<int> pre;
vector<vector<int> > c;
deque<int> q;

int bfs_1(int s,int t)
{
    f.resize(0);
    f.resize(c.size(),0);
    f[s]=oo_max;
    pre.resize(0);
    pre.resize(c.size(),-1);
    pre[s]=s;
    q.resize(0);
    for (q.push_back(s);(!q.empty())&&pre[t]==-1;q.pop_front())
    {
        int now=q.front();
        for (int i=0;i<c.size();i++)
            if (c[now][i]&&pre[i]==-1)
            {
                pre[i]=now;
                f[i]=min(c[now][i],f[now]);
                q.push_back(i);
            }
    }
    return ((pre[t]!=-1)?f[t]:-1);
}

int max_flow_1(int s,int t)
{
    int temp=0,ans=0;
    while ((temp=bfs_1(s,t))!=-1)
    {
        for (int i=t;i!=s;i=pre[i])
            c[pre[i]][i]-=temp,c[i][pre[i]]+=temp;
        ans+=temp;
    }
    return ans;
}

int main()
{
    while (~scanf("%d",&T))
        for (int t=1;t<=T;t++)
        {
            scanf("%d%d",&n,&m);
            c.resize(0);
            c.resize(2*(n+1));
            for (int i=0;i<c.size();i++)
                c[i].resize(c.size(),0);
            for (int i=1;i<n;i++)
                scanf("%d",&c[n+1+i][i]);
            for (int i=1;i<=m;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                c[x][n+1+y]=c[y][n+1+x]=oo_max;
            }
            c[2*n+1][n]=oo_max;
            int ans=max_flow_1(0,n);
            if (ans==0)
                printf("Min!\n");
            else if (ans>=oo_max)
                printf("Max!\n");
            else
                printf("%d\n",ans);
        }
}

60分的同学慎用break！！
泪了

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1152 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 1152 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 1152 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 1152 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 1152 KiB, score = 10

测试数据 #5: Accepted, time = 14 ms, mem = 1152 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 1152 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 1152 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 1152 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 1152 KiB, score = 10

Summary: Accepted, time = 104 ms, mem = 1152 KiB, score = 100

EK AC!!!

编译通过...├ 测试数据 01：答案正确...ms├ 测试数据 02：答案正确...ms├ 测试数据 03：答案正确...ms├ 测试数据 04：答案正确...ms├ 测试数据 05：答案正确...ms├ 测试数据 06：答案正确...ms├ 测试数据 07：答案正确...ms├ 测试数据 08：答案正确...ms├ 测试数据 09：答案正确...ms├ 测试数据 10：答案正确...msAccepted 有效得分：100 有效耗时：0ms

膜拜332404521。。。。

“螃蟹都知道的最小割最大流定理”：我一开始就10分，不过现在不是螃蟹了。。。

好……拆啊

这点拆的 - - 明天再写

Accepted 有效得分：100 有效耗时：0ms

一遍ac~~刚好99人~~

明显的拆点最大流吗~~usaco上都有的……

网络流终于越打越算了~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

之前没有拆点把一边上两点权小的一个作为边容量，0和N的权设成最大，然后直接网络流，结果70分。

看了楼下牛们的题解才知道要拆点，就AC了。

可是为什么不拆点就错呢，请指教！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

晕死的拆点

一个点a拆成a和a'

然后若两点a、b相连则

a和b'连接

a'和b连接

一定要记住每次把容量数组清零

洪水如果足够猛,

确实可以双向.

题目描述应该说清楚呀

我开始以为有拓扑关系,

记忆化递归就是死循环.

权当练习拆点最小割………………

最大流做出来是0就是不可达，无穷大就是阻止不了

开始居然把这么重要的条件忘了 - -！

真是搞笑把maxint改成maxlongint

一下子多对9个点

编译通过...

[red]

构图很简单

就是求最大流

我用的是sap+gap

注意河流是双向的

我菜啊

居然被exit

搞成60分

搞了我很久

太没用了

注意

exit

使用

这种题原创出来有什么用！

类似的题目已经够多了

50分超时可能是没考虑Max！的情况

这个比较像无穷吧: oo