최소 절단 문제 에 대한 약간의 사고

최소 절단 문제 에 대한 약간의 사고
다시 명확 하 게 정의 하 다
스 트림 네트워크 는 그림 에 정의 되 어 있 습 니 다.무방 향 도 를 유향 도로 뜯 어 내다.안 뜯 어도 돼.
최소 베 기 는 하나의 사 이 드 집합 \ (S, T) \), 점 을 \ (S, T = V - S \) 두 개의 집합 으로 나 눕 니 다.
최소 용량 \ (c (S, T) = \ sum {u \ in S} \ \ sum {v \ in T} c (u, v) \)
그래서 모든 변 을 삭제 하고 집중 한 후에 s 에서 t 까지 연결 되 지 않 습 니 다.최대 흐름 후 할 집 된 변 (s 에서 t 방향) 이 만 류 됩 니 다.
(t 에서 s 까지 꼭 그렇지 는 않다.)
최소 절단 의 유일 성
최대 흐름 후의 잔 량 네트워크 에서 만 류 된 변 은 반드시 가장 자 리 를 자 르 는 것 이 아니 라 가장 자 리 를 자 르 면 반드시 만 류 된다.
최소 절단 용량 은 절단 변 의 용량 과 최대 흐름 의 유량 과 같다.
최소 베 기 는 점 집합 이 유일 하 다 는 것 을 의미한다.
유일 성 판정:
강 한 연결 분량 (하나의 점 일 수 있 음) \ (u \) 이 존재 하여 잔 량 네트워크 에 s 에서 u 와 u 에서 t 까지 의 경로 가 없 음 을 만족 시 키 면 u 는 \ (S \) 또는 \ (T \) 에 분 배 될 수 있 으 며 최소 분할 이 유일 하지 않 습 니 다.
그래서 s 부터 bfs 를 시작 하고 t 에서 bfs 를 거꾸로 하 는 것 입 니 다.
전형 적 인 밤 1, 2, 1, 2, 3, 1, 2, 3, 1, 3, 4, 1.
scc 의 판정 방법 을 구하 십시오:
어떤 쪽 이 집중 할 수 있 는 지, 반드시 집중 할 수 있 는 지 를 판단 하 다.
scc 를 구하 고 판정 합 니 다.
scc 를 구 한 후 scc 사이 에 연 결 된 단 방향 변 은 한 방향 으로 만 류 되 기 때 문 임 을 알 수 있 습 니 다.
jcvb：
잔여 네트워크 에서 tarjan 을 뛰 어 다 니 며 모든 SCC 를 구하 고 id [u] 를 점 u 가 있 는 SCC 의 번호 로 기록 합 니 다.분명히 id [s] 가 있 습 니 다! =id [t] (그렇지 않 으 면 s 에서 t 까지 통로 가 있 고 계속 확대 할 수 있 습 니 다).

임의의 만 류 변 (u, v) 에 대해 (u, v) 은 특정한 최소 분할 집중 에 나타 날 수 있 고 id [u] 로 만 나타 날 수 있 습 니 다! =id[v]；

임의의 만 류 변 (u, v) 에 대해 (u, v) 은 반드시 최소 분할 집중 에 나타 나 고 id [u] = id [s] 와 id [v] = id [t] 만 나타 납 니 다.

증명:
①
< = = 각 SCC 를 하나의 점 으로 축소 하여 얻 은 새 그림 은 만 류 변 만 포함 합 니 다.그러면 새 그림 의 모든 s - t 베 기 는 원래 그림 의 최소 베 기 에 대응 하고 그 중에서 id [u] 와 id [v] 를 자 르 는 것 을 선택 하면 증명 할 수 있 습 니 다.
② < = =: (u, v) 의 변 권 을 확대 한다 고 가정 하면 잔여 네트워크 에 s - > u - > v - > t 의 통로 가 나타 나 계속 넓 어 질 수 있 기 때문에 최대 유량 (즉 최소 용량) 이 커진다.이것 은 (u, v) 이 최소 절단 집중 에 반드시 나타 나 야 하 는 변 이라는 것 을 설명 한다.
PS: 무방 향도
역방향 아크 용량 은 c 이 므 로 두 번 추가 할 필요 가 없다.
QwQ 두 번 추가 가능 합 니 다.
템 플 릿 두 개

//zoj2587
#include 
#include 
#include 
#include 
using namespace std;
const int N = 1005, M = 20005, inf = 1e9;

int n, m, s, t;

struct edge {int v, ne, c, f;} e[M];
int cnt = 1, h[N];
inline void ins(int u, int v, int c) {
    e[++cnt] = (edge) {v, h[u], c, 0}; h[u] = cnt;
    e[++cnt] = (edge) {u, h[v], c, 0}; h[v] = cnt;
}
int cur[N], vis[N], d[N], head, tail, q[N];
bool bfs() {
    memset(vis, 0, sizeof(vis));
    head = tail = 1;
    q[tail++] = s; d[s] = 0; vis[s] = 1;
    while(head != tail) {
        int u = q[head++];
        for(int i=h[u]; i; i=e[i].ne) {
            int v = e[i].v;
            if(!vis[v] && e[i].c > e[i].f) {
                vis[v] = 1;
                d[v] = d[u] + 1;
                q[tail++] = v;
                if(v == t) return true;
            }
        }
    }
    return false;
}
int dfs(int u, int a) { //printf("dfs %d %d
", u, a);
    if(u==t || a==0) return a;
    int flow = 0, f;
    for(int &i=cur[u]; i; i=e[i].ne) {
        int v = e[i].v;
        if(d[v] == d[u]+1 && (f = dfs(v, min(a, e[i].c-e[i].f))) > 0) {
            flow += f;
            e[i].f += f;
            e[i^1].f -= f;
            a -= f;
            if(a == 0) break;
        }
    }
    if(a) d[u] = -1;
    return flow;
}
int dinic() {
    int flow = 0;
    while(bfs()) {
        for(int i=1; i<=n; i++) cur[i] = h[i];
        flow += dfs(s, inf);
    }
    return flow;
}


int bfs2(int s) {
    int ans = 1;
    memset(vis, 0, sizeof(vis));
    head = tail = 1;
    q[tail++] = s; vis[s] = 1;
    while(head != tail) {
        int u = q[head++];
        for(int i=h[u]; i; i=e[i].ne) {
            int v = e[i].v;
            if(vis[v] || e[i].c==e[i].f) continue;
            vis[v] = 1;
            ans++;
            q[tail++] = v;
        }
    }
    return ans;
}

int bfs3(int s) {
    int ans = 1;
    memset(vis, 0, sizeof(vis));
    head = tail = 1;
    q[tail++] = s; vis[s] = 1;
    while(head != tail) {
        int u = q[head++];
        for(int i=h[u]; i; i=e[i].ne) {
            int v = e[i].v;
            if(vis[v] || e[i^1].c==e[i^1].f) continue;
            vis[v] = 1;
            ans++;
            q[tail++] = v;
        }
    }
    return ans;
}

int main() {
    freopen("in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(); cout.tie();

    while(true) {
        cin >> n >> m >> s >> t;
        if(n == 0) break;
        cnt = 1;
        memset(h, 0, sizeof(h));
        for(int i=1; i<=m; i++) { 
            int u, v, c;
            cin >> u >> v >> c;
            ins(u, v, c);
        }
        dinic();
        int cnt1 = bfs2(s), cnt2 = bfs3(t);
        if(cnt1 + cnt2 < n) cout << "AMBIGUOUS" << endl;
        else cout << "UNIQUE" << endl;
    }
}

//[AHOI2009]   
#include 
#include 
#include 
#include 
using namespace std;
const int N = 4005, M = 6e4+5, inf = 1e9;

int n, m, s, t;
struct edge {int u, v, ne, c, f;} e[M<<1];
int cnt=1, h[N];
inline void ins(int u, int v, int c) {
    e[++cnt] = (edge) {u, v, h[u], c, 0}; h[u] = cnt;
    e[++cnt] = (edge) {v, u, h[v], 0, 0}; h[v] = cnt;
}
int cur[N], vis[N], d[N], head, tail, q[N];
bool bfs() {
    memset(vis, 0, sizeof(vis));
    head = tail = 1;
    q[tail++] = s; d[s] = 0; vis[s] = 1;
    while(head != tail) {
        int u = q[head++];
        for(int i=h[u]; i; i=e[i].ne) {
            int v = e[i].v;
            if(!vis[v] && e[i].c > e[i].f) {
                vis[v] = 1;
                d[v] = d[u]+1;
                q[tail++] = v;
                if(v == t) return true;
            }
        }
    }
    return false;
}
int dfs(int u, int a) {
    if(u==t || a==0) return a;
    int flow = 0, f;
    for(int &i=cur[u]; i; i=e[i].ne) {
        int v = e[i].v;
        if(d[v] == d[u]+1 && (f = dfs(v, min(a, e[i].c-e[i].f))) > 0) {
            flow += f;
            e[i].f += f;
            e[i^1].f -= f;
            a -= f;
            if(a == 0) break;
        }
    }
    if(a) d[u] = -1;
    return flow;
}
int dinic() {
    int flow = 0;
    while(bfs()) {
        for(int i=1; i<=n; i++) cur[i] = h[i];
        flow += dfs(s, inf);
    }
    return flow;
}

int dfn[N], low[N], dfc, scc, belong[N], st[N], top;
void dfs(int u) {
    dfn[u] = low[u] = ++dfc;
    st[++top] = u;
    for(int i=h[u]; i; i=e[i].ne) if(e[i].c > e[i].f) {
        int v = e[i].v;
        if(!dfn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if(!belong[v]) 
            low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        scc++;
        while(true) {
            int x = st[top--];
            belong[x] = scc;
            if(x == u) break;
        }
    }
}

int main() {
    freopen("in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(); cout.tie();
    cin >> n >> m >> s >> t;
    for(int i=1; i<=m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        ins(u, v, c);
    }
    dinic();
    for(int i=1; i<=n; i++) if(!dfn[i]) dfs(i);
    //for(int i=1; i<=n; i++) printf("dfn %d %d %d
", i, dfn[i], belong[i]);

    int a = belong[s], b = belong[t];
    for(int i=1; i<=m; i++) {
        int u = e[i<<1].u, v = e[i<<1].v;
        if(e[i<<1].c == e[i<<1].f && belong[u] != belong[v]) cout << 1 << ' ';
        else cout << 0 << ' ';
        if(e[i<<1].c == e[i<<1].f && belong[u] == a && belong[v] == b) cout << 1 << '
';
        else cout << 0 << '
';
    }
}