NC19887. [AHOI2009]MINCUT 最小割
描述
输入描述
第一行有4个正整数，依次为N,M,s和t。
第2行到第(M+1)行每行3个正整数v,u,c表示v中转站到u中转站之间有单向道路相连，单向道路的起点是v，终点是u,切断它的代价是c(1 ≤ c ≤ 100000)。
注意:两个中转站之间可能有多条道路直接相连。同一行相邻两数之间可能有一个或多个空格。
输出描述
对每条单向边，按输入顺序，依次输出一行，包含两个非0即1的整数，分别表示对问题一和问题二的回答(其中输出1表示是，输出0表示否)。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
示例1
输入:
6 7 1 6 1 2 3 1 3 2 2 4 4 2 5 1 3 5 5 4 6 2 5 6 3
输出:
1 0 1 0 0 0 1 0 0 0 1 0 1 0
说明:
设第(i+1)行输入的边为i号边，那么{1,2},{6,7},{2,4,6}是仅有的三个最小代价切割方案。它们的并是{1,2,4,6,7}，交是 {∅} 。C++14(g++5.4) 解法, 执行用时: 44ms, 内存消耗: 3096K, 提交时间: 2020-08-19 19:27:25
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
const int inf = 2e9;
const int max_n = 4e3 + 100;
const int max_m = 1e6 + 100;
int n, m;int s, t;
int us[max_m], vs[max_m];
struct edge
{
int to, cap, rev, next;
}E[max_m * 2];
int head[max_n];
int cnt = 1;
void add(int from, int to,int cap) {
E[cnt].to = to;E[cnt].cap = cap;
E[cnt].rev = cnt + 1;
E[cnt].next = head[from];
head[from] = cnt++;
E[cnt].to = from;E[cnt].cap = 0;
E[cnt].rev = cnt - 1;
E[cnt].next = head[to];
head[to] = cnt++;
}
int iter[max_n];
int dist[max_n];
bool searchpath(int s, int t) {
fill(dist, dist + 1 + n, -1);
queue<int> que;dist[s] = 0;
que.push(s);
while (!que.empty()) {
int u = que.front();que.pop();
for (int i = head[u];i;i = E[i].next) {
edge& e = E[i];
if (dist[e.to] != -1 || e.cap == 0)continue;
dist[e.to] = dist[u] + 1;
que.push(e.to);
}
}return dist[t] != -1;
}
int matchpath(int u, int t, int f) {
if (u == t)return f;
for (int& i = iter[u];i;i = E[i].next) {
edge& e = E[i];
if (dist[e.to] <= dist[u] || e.cap == 0)continue;
int d = matchpath(e.to, t, min(f, e.cap));
if (d <= 0)continue;
e.cap -= d;E[e.rev].cap += d;
return d;
}return false;
}
int dinic(int s,int t) {
int flow = 0;int f;
while (searchpath(s, t)) {
for (int i = 1;i <= n;i++)iter[i] = head[i];
while (f = matchpath(s, t, inf))
flow += f;
}return flow;
}
int dfn[max_n], low[max_n], color[max_n];
int tot = 0, colour = 0;
stack<int> st;
void tarjan(int u) {
dfn[u] = low[u] = tot++;st.push(u);
for (int i = head[u];i;i = E[i].next) {
edge& e = E[i];
if (!e.cap)continue;
if (!dfn[e.to]) { tarjan(e.to);low[u] = min(low[u], low[e.to]); }
else if (color[e.to] == 0)low[u] = min(low[u], dfn[e.to]);
}if (dfn[u] != low[u])return;
colour++;
while (st.top() != u) {
color[st.top()] = colour;
st.pop();
}color[st.top()] = colour;st.pop();
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m >> s >> t;
for (int i = 1;i <= m;i++) {
int cap;
cin >> us[i] >> vs[i] >> cap;
add(us[i], vs[i], cap);
}dinic(s, t);
for (int i = 1;i <= n;i++)
if (!dfn[i])tarjan(i);
for (int i = 1;i <= m;i++) {
edge& e = E[i * 2 - 1];
if (e.cap || color[us[i]] == color[vs[i]])
cout << "0 0\n";
else if (color[us[i]] == color[s] && color[vs[i]] == color[t])
cout << "1 1\n";
else
cout << "1 0\n";
}
}
C++11(clang++ 3.9) 解法, 执行用时: 56ms, 内存消耗: 9548K, 提交时间: 2020-10-08 19:15:08
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=4e3+5,M=5e5+5,Inf=1e9;
struct Graph{int u,v;}g[M];
struct Edge{int to,f,nxt;}e[M<<1];
int n,m,s,t,fst[N],nf[N],tote,lev[N],q[N],hd,tl;
void adde(int u,int v,int w){
e[++tote]=(Edge){v,w,fst[u]};fst[u]=tote;
e[++tote]=(Edge){u,0,fst[v]};fst[v]=tote;
}
bool bfs(){
for(int i=1;i<=n;i++)lev[i]=-1;
q[hd=tl=1]=s;lev[s]=0;
while(hd<=tl){
int u=q[hd++];
for(int i=fst[u],v;~i;i=e[i].nxt)if(e[i].f&&lev[v=e[i].to]<0)
lev[v]=lev[u]+1,q[++tl]=v;
}
return lev[t]>=0;
}
int dfs(int u,int lim){
if(u==t)return lim;
int res=0;
for(int i=nf[u],v,f;~i;i=e[i].nxt){
v=e[i].to;f=e[i].f;
if(lev[v]==lev[u]+1&&f){
int tmp=dfs(v,min(lim,f));
e[i].f-=tmp;e[i^1].f+=tmp;lim-=tmp;res+=tmp;
if(!lim){nf[u]=i;return res;}
}
}
nf[u]=-1;return res;
}
int dfn[N],low[N],id,st[N],tp,bel[N],tot;
vector<int>adj[N];
map<int,bool>lk[N];
void chkmi(int &x,int y){x=x<y?x:y;}
void addnew(int u,int v){adj[u].pb(v);lk[u][v]=true;}
void tarjan(int u){
dfn[u]=low[u]=++id;st[++tp]=u;
for(auto v:adj[u])if(!dfn[v])tarjan(v),chkmi(low[u],low[v]);else if(!bel[v])chkmi(low[u],dfn[v]);
if(dfn[u]==low[u]){
tot++;
while(st[tp]!=u)bel[st[tp]]=tot,tp--;
bel[st[tp]]=tot;tp--;
}
}
int main(){
memset(fst,-1,sizeof(fst));tote=1;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1,u,v,w;i<=m;i++)scanf("%d%d%d",&u,&v,&w),adde(u,v,w),g[i]=(Graph){u,v};
int flow=0;
while(bfs())memcpy(nf,fst,sizeof(nf)),flow+=dfs(s,Inf);
//printf("%d\n",flow);
for(int u=1;u<=n;u++)for(int i=fst[u];~i;i=e[i].nxt)
if(e[i].f)addnew(u,e[i].to);
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
//for(int i=1;i<=n;i++)printf("%d%c",bel[i]," \n"[i==n]);
for(int i=1,u,v;i<=m;i++){
u=g[i].u;v=g[i].v;
if(lk[u][v]||bel[u]==bel[v])puts("0 0");
else{
printf("1 ");
if(bel[s]==bel[u]&&bel[v]==bel[t])puts("1");else puts("0");
}
}
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 52ms, 内存消耗: 3216K, 提交时间: 2023-02-28 19:31:57
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
using ll=long long;
int n,m,s,t;
int hd[N],ed[N],to[N];
struct Eg{int x,y;}g[N];
ll flow,w[N];
void run(){
static int d[N],q[N],l,r,nw[N];
function<bool()>bfs=[&](){
int i,x,y;
for(x=1;x<=n;++x)d[x]=0,nw[x]=hd[x];
d[q[l=r=1]=t]=1;
while(l<=r){
x=q[l++];
for(i=hd[x];i;i=to[i])
w[i^1]&&!d[y=ed[i]]&&(d[q[++r]=y]=d[x]+1);
}return d[s];
};
function<ll(int,ll)>dc=[&](int x,ll fl){
if(x==t)return fl;
int y;ll k,rs=fl;
for(int &i=nw[x];i;i=to[i])
if(w[i]&&d[y=ed[i]]==d[x]-1&&(k=dc(y,min(w[i],rs)))){
w[i]-=k,w[i^1]+=k;if(!(rs-=k))return fl;
}return fl-rs;
};
ll k;while(bfs())while(k=dc(s,1e18))flow+=k;
}
int dfn[N],inc[N],scc;
void tarjan(int x){
static int low[N],dlt,stk[N],tp;
int i,y;
dfn[x]=low[x]=++dlt;
stk[++tp]=x;
for(i=hd[x];i;i=to[i])
if(w[i]){
if(dfn[y=ed[i]]){
(!inc[y])&&low[x]>dfn[y]&&(low[x]=dfn[y]);
}else{
tarjan(y);
low[x]>low[y]&&(low[x]=low[y]);
}
}
if(dfn[x]==low[x]){
++scc;do{
inc[stk[tp]]=scc;
}while(stk[tp--]!=x);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>s>>t;
int i,j,k,l,r,x,y;
for(i=1;i<=m;++i){
cin>>x>>y>>w[i+i],g[i]={x,y};
to[i+i]=hd[ed[i+i+1]=x],hd[x]=i+i;
to[i+i+1]=hd[ed[i+i]=y],hd[y]=i+i+1;
}run();
for(x=1;x<=n;++x)
if(!dfn[x])tarjan(x);
for(i=1;i<=m;++i)
printf("%d %d\n",!w[i+i]&&inc[g[i].x]!=inc[g[i].y],
!w[i+i]&&inc[g[i].x]==inc[s]&&inc[g[i].y]==inc[t]);
return 0;
}