点割集

struct node{
long v,next;
long val;
} s[maxm*2];
long level[maxn],p[maxn],que[maxn],out[maxn],ind;
inline void insert(long x,long y,long z)
{
s[ind].v=y;
s[ind].val=z;
g[i][i]=0;
}
if(g[start][end]==1)
{
printf("NO ANSWER!\n");
continue;
}
memset(cut,0,sizeof(cut));
build(n);
int maxflow=dinic(n*2,start,end+n);
vector<int>v;
if(maxflow==0)printf("0\n");
{
int m,n,x,y,start,end;
//freopen("a.txt","r",stdin);
while(scanf("%d%d%d",&n,&start,&end)!=EOF)
{
int i,j;
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)scanf("%d",&g[i][j]);
memset(map,0,sizeof(map));
memset(mark,0,sizeof(mark));
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
f[i][j]=inf;
}
}
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
map[x][y]=1;
{
if(s[i].val&&out[s[i].v]!=-1&&level[u]+1==level[s[i].v])
{
break;
}
}
if(i!=-1)
{
que[++q]=i;
out[u]=s[i].next;
}
else//当前点没有临接的可行流
{
out[u]=-1;
q--;
}
}
}
}
return ret;
}
}
ret+=dd;
for(i=0; i<=q; i++)
{
s[que[i]].val-=dd;
s[que[i]^1].val+=dd;
}
for(i=0; i<=q; i++)//堵塞点
{
if(s[que[i]].val==0)
{
q=i-1;
break;
}
}
}
else
{
for(i=out[u]; i!=-1; i=s[i].next)
bool mark[maxn];
struct node{
long v,next;
long val;
} s[maxm*2];
long level[maxn],p[maxn],que[maxn],out[maxn],ind;
long min(int x,int y){return x>y?y:x;}
inline void insert(long x,long y,long z)
}
}
build(n);
maxflow = dinic(n*2,start,end+n);
printf("%d\n",maxflow);
}
return 0;
}
}
}
if(i!=-1)
{
que[++q]=i;
out[source]=s[i].next;
}
else break;
}
long u=s[que[q]].v;
if(u==sink)
{
long dd=inf;
for(i=0; i<=q; i++)
{
if(dd>s[que[i]].val)
{
dd=s[que[i]].val;
}
}
}
}
long dinic(long n,long source,long sink)
{
long ret=0,i;
while(1)
{
build_level(n,source);
if(level[sink]==0)break;
for(i=0; i<=n; ++i)out[i]=p[i];//有一次写错了'='，结果tle，调试了好久
字典序：
就是个点从i=1开始统计即可
#include <iostream>
#include <vector>
using namespace std;
const long maxn=400;
const long maxm=160002;
const long inf=0x7fffffff;
int g[maxn][maxn],cut[maxn];
}
void floyd(int n)
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j||i==k||j==k)continue;
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
s[ind].next=p[x];
p[x]=ind;
ind++;
s[ind].v=x;
s[ind].val=0;
s[ind].next=p[y];
p[y]=ind;
ind++;
}
void build_level(int n,int source)
{
int h=0,r=0,i,u;
for(i=0;i<=n; i++)level[i]=0;
}
}
if(i!=-1)
{
que[++q]=i;
out[source]=s[i].next;
}
else break;
}
long u=s[que[q]].v;
if(u==sink)
{
long dd=inf;
for(i=0; i<=q; i++)
{
if(dd>s[que[i]].val)
{
dd=s[que[i]].val;
level[s[i].v]=level[u]+1;
}
}
}
}
long dinic(long n,long source,long sink)
{
long ret=0,i;
while(1)
{
build_level(n,source);
if(level[sink]==0)break;
for(i=0; i<=n; ++i)out[i]=p[i];//有一次写错了'='，结果tle，调试了好久
maxflow=res;
}
else cut[i]=0;
if(res==0)break;
}
for(i=0; i<v.size()-1; i++)printf("%d ",v[i]);
printf("%d\n",v[i]);
}
}
return 0;
}
hdu 2485 最短路构图，然后求最小点割集
#include <iostream>
pku 1815 最小点割集 拆点 要求割集字典序输出
拆点：
for(i=1; i<=n; i++)
{
insert(n+i,i,1-cut[i]);
for(j=1; j<=n; j++)if(g[i][j])insert(i,n+j,inf);
}
去掉某个点检查从start到end的最大流是否变小，如果是这个就是其中的割点
#include <vector>
#include <string.h>
#include <stdio.h>
using namespace std;
#define maxm 1140080
#define maxn 200
const long inf=0x3fffffff;
int f[maxn][maxn],map[maxn][maxn];
long q=-1;
while(1)
{
if(q<0)//空栈中，压入source（如果source的临接边没有满流）
{
for(i=out[source];i!=-1; i=s[i].next)
{
if(s[i].val&&out[s[i].v]!=-1&&level[s[i].v]==2)
{
break;
{
if(s[i].val&&out[s[i].v]!=-1&&level[u]+1==level[s[i].v])
{
break;
}
}
if(i!=-1)
{
que[++q]=i;
out[u]=s[i].next;
}
else//当前点没有临接的可行流
{
out[u]=-1;
q--;
}
}
}
}源自文库
return ret;
long q=-1;
while(1)
{
if(q<0)//空栈中，压入source（如果source的临接边没有满流）
{
for(i=out[source];i!=-1; i=s[i].next)
{
if(s[i].val&&out[s[i].v]!=-1&&level[s[i].v]==2)
{
break;
{
s[ind].v=y;
s[ind].val=z;
s[ind].next=p[x];
p[x]=ind;
ind++;
s[ind].v=x;
s[ind].val=0;
s[ind].next=p[y];
p[y]=ind;
ind++;
}
void build_level(int n,int source)
{
int h=0,r=0,i,u;
f[x][y]=1;
}
if(map[1][n])
{
printf("0\n");
continue;
}
for(i=1;i<=n;i++)map[i][i]=0;
floyd(n);
mark[1]=mark[n]=1;
for(i=2;i<n;i++)
{
if(f[1][i]+f[i][n]<=k)
{
mark[i]=1;
level[source]=1;
que[0]=source;
while(h<=r)
{
u=que[h++];
for(i=p[u]; i!=-1; i=s[i].next)
{
if(s[i].val&&level[s[i].v]==0)
{
que[++r]=s[i].v;
level[s[i].v]=level[u]+1;
else
{
printf("%d\n",maxflow);
for(i=1; i<=n; i++)
{
if(i==start||i==end)continue;
cut[i]=1;
build(n);
int res=dinic(2*n,start,end+n);
if(res<maxflow)
{
v.push_back(i);
}
}
}
int main()
{
int maxflow,end,start,n,m,x,y;
int i,k,j;
//freopen("a.txt","r",stdin);
while(scanf("%d%d%d",&n,&m,&k))
{
if(n==0&&m==0&&k==0)break;
start=1;
end=n;
for(i=0;i<=n; i++)level[i]=0;
level[source]=1;
que[0]=source;
while(h<=r)
{
u=que[h++];
for(i=p[u]; i!=-1; i=s[i].next)
{
if(s[i].val&&level[s[i].v]==0)
{
que[++r]=s[i].v;
}
}
}
void build(int n)
{
int i, j;
memset(p, -1, sizeof(p));
ind= 0;
for(i = 1; i <= n; i++)
{
if(mark[i])
{
insert(n + i, i, 1);
for(j = 1; j <= n; j++)
if(map[i][j]&&mark[j]) insert(i, n + j, inf);
}
}
ret+=dd;
for(i=0; i<=q; i++)
{
s[que[i]].val-=dd;
s[que[i]^1].val+=dd;
}
for(i=0; i<=q; i++)//堵塞点
{
if(s[que[i]].val==0)
{
q=i-1;
break;
}
}
}
else
{
for(i=out[u]; i!=-1; i=s[i].next)
}
void build(int n)
{
int i,j;
ind=0;
memset(p,-1,sizeof(p));
for(i=1; i<=n; i++)
{
insert(n+i,i,1-cut[i]);
for(j=1; j<=n; j++)if(g[i][j])insert(i,n+j,inf);
}
}
int main()