BZOJ 1797最小割
3375 ワード
タイトルリンク:http://61.187.179.132/JudgeOnline/problem.php?id=1797
題意:有向図を与え、各辺に流量があり、ソースポイントの合流点s、tを与える.各エッジについて、(1)最小分割がそのエッジを含むかどうかを尋ねます.(2)すべての最小カットにそのエッジが含まれていますか?
構想:まず最大ストリームを求め、残りのネットワークの中で強い連通成分を求める.各原図中のエッジ(最大ストリームに追加された逆エッジは計算されない)について、エッジの残留流量が0であり、uとvが2つの異なる強い連通成分にある場合、最小分割がエッジを含む.上記で満たされ、uとsは、1つの連通成分、vとtが1つの連通成分である場合に、すべての最小分割がこのエッジを含む.
題意:有向図を与え、各辺に流量があり、ソースポイントの合流点s、tを与える.各エッジについて、(1)最小分割がそのエッジを含むかどうかを尋ねます.(2)すべての最小カットにそのエッジが含まれていますか?
構想:まず最大ストリームを求め、残りのネットワークの中で強い連通成分を求める.各原図中のエッジ(最大ストリームに追加された逆エッジは計算されない)
struct node
{
int u,v,cap,id,next;
};
node edges[N*50];
int head[N],e;
int pre[N],num[N],h[N],cur[N];
int s,t;
int Maxflow(int s,int t,int n)
{
int i;
for(i=0;i<n;i++) cur[i]=head[i];
int u=s,Min,k,v,ans=0;
while(h[u]<n)
{
if(u==t)
{
Min=INF;
for(i=s;i!=t;i=edges[cur[i]].v)
{
k=cur[i];
if(edges[k].cap<Min) Min=edges[k].cap,v=i;
}
ans+=Min; u=v;
for(i=s;i!=t;i=edges[cur[i]].v)
{
k=cur[i];
edges[k].cap-=Min;
edges[k^1].cap+=Min;
}
}
for(i=cur[u];i!=-1;i=edges[i].next)
{
if(edges[i].cap>0&&h[u]==h[edges[i].v]+1) break;
}
if(i!=-1)
{
cur[u]=i;
pre[edges[i].v]=u;
u=edges[i].v;
}
else
{
if(--num[h[u]]==0) break;
cur[u]=head[u];
Min=n;
for(i=head[u];i!=-1;i=edges[i].next)
{
if(edges[i].cap>0&&h[edges[i].v]<Min) Min=h[edges[i].v];
}
h[u]=Min+1;
num[Min+1]++;
if(u!=s) u=pre[u];
}
}
return ans;
}
int n,m;
void add(int u,int v,int w,int id)
{
edges[e].u=u;
edges[e].v=v;
edges[e].cap=w;
edges[e].id=id;
edges[e].next=head[u];
head[u]=e++;
}
int dfn[N],low[N],id,Num,color[N],visit[N];
stack<int> S;
void DFS(int u)
{
low[u]=dfn[u]=++id;
S.push(u);
int i,v;
for(i=head[u];i!=-1;i=edges[i].next)
{
v=edges[i].v;
if(edges[i].cap<=0) continue;
if(!dfn[v])
{
DFS(v);
low[u]=min(low[u],low[v]);
}
else if(!visit[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
Num++;
do
{
v=S.top();
S.pop();
visit[v]=1;
color[v]=Num;
}while(v!=u);
}
}
int ans[N*30][2];
int main()
{
clr(head,-1);
RD(n,m); RD(s,t);
int u,v,w,i;
FOR1(i,m)
{
RD(u,v,w);
add(u,v,w,i);
add(v,u,0,0);
}
Maxflow(s,t,n+1);
FOR1(i,n) if(!visit[i]) DFS(i);
FOR0(i,e)
{
u=edges[i].u;
v=edges[i].v;
w=edges[i].id;
if(color[u]==color[v]) continue;
if(edges[i].cap>0) continue;
ans[w][0]=1;
if(color[u]==color[s]&&color[v]==color[t])
{
ans[w][1]=1;
}
}
FOR1(i,m) PR(ans[i][0],ans[i][1]);
}