题目链接：http://hihocoder.com/problemset/problem/1378?sid=1551012
题目大意：

思路：跑出最大流，再bfs一次残剩网络，满流的边不跑就得到了割点集。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=2e5+10;

struct E
{
    int v;   //每一条边指向的点
    int next;//指向对应点的前一条边
    int w;   //每一条边的残量

}e[maxm];

int s, t;//源点和汇点
int cut;//边的数量，从0开始编号
int head[maxm];//每一个点最后一条边的编号
int d[maxn];//分层图中标记深度
int inf=(1<<31)-1;
int cur[maxn];//cur就是记录当前点u循环到了哪一条边
int n, m;

void init()
{
    cut=-1;
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v, int w)
{
    cut++;
    e[cut].next=head[u];
    e[cut].v=v;
    e[cut].w=w;
    head[u]=cut;
}

void add(int u, int v, int w)
{
    addEdge(u, v, w);
    addEdge(v, u, 0);
}

int bfs()
{
    queue<int> q;
    while(!q.empty())
    {
        q.pop();
    }
    memset(d, 0, sizeof(d));
    d[s]=1;//源点深度为1
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].v, w=e[i].w;
            if(w>0&&d[v]==0)//若该残量不为0，且V[i]还未分配深度，则给其分配深度并放入队列
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    if(d[t]==0)//当汇点的深度不存在时，说明不存在分层图，同时也说明不存在增广路
    {
        return 0;
    }

    return 1;
}

int dfs(int u, int dis)//u是当前节点，dist是当前流量
{
    if(u==t)
    {
        return dis;//当已经到达汇点，直接返回
    }

    for(int &i=cur[u];i!=-1;i=e[i].next)
    {
        int v=e[i].v, w=e[i].w;
        if((d[v]==d[u]+1)&&w!=0)//注意这里要满足分层图和残量不为0两个条件
        {
            int di=dfs(v, min(dis, w));//向下增广
            if(di>0)//若增广成功
            {
                e[i].w-=di;//正向边减
                e[i^1].w+=di;//反向边加
                return di;//向上传递
            }
        }
    }

    return 0;//否则说明没有增广路，返回0
}

int Dinic()
{
    int ans=0;//记录最大流量
    while (bfs())
    {
        /*******************************/
        for(int i=s;i<=t;i++)//每一次建立完分层图后都要把cur置为每一个点的第一条边
        {
            cur[i]=head[i];
        }
        /********************************/
        while (int d=dfs(s,inf))
        {
            ans+=d;
        }
    }
    return ans;
}

vector<int> v;
queue<int> q;
void minzxg(){//最小割集

    memset(d, 0, sizeof(d));
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        v.push_back(u);
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v, w=e[i].w;
            if(d[v]==0&&w>0){
                d[v]=1;
                q.push(v);
            }
        }
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        v.clear();
        init();
        s=1, t=n;
        for(int i=0;i<m;i++)
        {
            int u, v, w;
            scanf("%d%d%d",&u,&v,&w);
            add(u, v, w);
        }
        printf("%d ",Dinic());
        minzxg();
        sort(v.begin(), v.end());
        printf("%d\n", v.size());
        for(int i=0; i<v.size(); i++){
            printf("%d%c", v[i], (i==v.size()-1?'\n':' '));
        }
    }
    return 0;
}