[HZOI 2016]颓废元 - ztx - 366888

记录编号	366888	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]颓废元	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2017-01-26 13:22:52	内存使用	0.46 MiB
显示代码纯文本
/// by ztx

#include <bits/stdc++.h>

/***
 * ans1 ope 1 x边是否一定在最大流的边集中，重设x边两端点为S,T推流是否能推尽此边的流量, 复杂度未知
 - 题目描述错误，询问x边是否在某一最小割边集中。
 * ans2 ope 0 x边是否在所有最小割边集中，残量网络 dfs求S,T点集，x边两侧属于不同点集则在所有最小割边集中
 * ans3 最大流
 * ans4 字典序最小的最小割边集：
 * 从小到大枚举割边，并计算没有这条边的最大流，如最大流减少，则删去此边，记下此时的最大流，答案中加上此边；否则，不删边，枚举下一条边；直到最后最大流变为0.
 *
 */

int CH , NEG ;
template<typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Each(p,x)  for(p=x.begin();p!=x.end();p++)
#define  kN  410LL
#define  kM  4010LL
#define  oo  0x3f3f3f3fLL
#define  s(u)  star[u]
#define  t(p)  e[0][p]
#define  n(p)  e[1][p]
#define  f(p)  e[2][p]
#define  r(x)  read(x)
#define  min(x,y) ((x)<(y)?(x):(y))

int e[3][kM<<1], star[kN] , te = 1;
inline void Add(int u, int v, int cap) {
    te ++ , t(te) = v, f(te) = cap, n(te) = s(u), s(u) = te;
    te ++ , t(te) = u, f(te) = 0, n(te) = s(v), s(v) = te;
}

int N, S, T, h[kN], vh[kN];

int dfs(int u, int fu) {
int p, t = h[u]+1, f = 0, fv;
    if (u == T) return fu;
    for (p = s(u); p; p = n(p))
        if (f(p) && (h[t(p)]+1==h[u])) {
            fv = dfs(t(p), min(fu-f, f(p)));
            f += fv, f(p) -= fv, f(p^1) += fv;
            if (f==fu || h[S]==N) return f;
        }
    for (p = s(u); p; p = n(p))
        if (f(p)) t = min(t, h[t(p)]);
    if (--vh[h[u]] == 0) h[S] = N;
    else ++ vh[h[u]=t+1];
    return f;
}

inline int SAP() {
    int ret = 0;
    memset(vh, 0, sizeof vh);
    memset(h, 0, sizeof h);
    vh[S] = N;
    while (h[S] < N) ret += dfs(S,oo);
    return ret;
}

int vis[kN] = {0};
void dfs2(int u, int i) {
    vis[u] = i+1;
    for (int p = s(u); p; p = n(p))
        if (!vis[t(p)] && f(p^i)) dfs2(t(p), i) ;
}

int n, m, x[kM], y[kM], poi[kM];
bool ans2[kM] = {0};

std::vector<int>ans4_0, ans4_1;
std::vector<int>::iterator it;

inline void Judge() {
    int i, u, v, p;
    dfs2(S,0), dfs2(T,1);
    Rep (i,1,m) {
        u = x[i], v = y[i];
        if (!f(poi[i]) && vis[u] && vis[v] && vis[u]!=vis[v])
            ans2[i] = true, ans4_0.push_back(i);
        else if (!f(poi[i]) && (!vis[u] || !vis[v]))
            ans4_1.push_back(i);
    }
}

inline void ans1(int i) {
    if (f(poi[i])) { puts("0"); return; }
    int u = x[i] , v = y[i];
    if ((vis[u] || vis[v]) && (vis[u] != vis[v])) puts("1");
    else if (!vis[u] && !vis[v]) puts("1");
    else puts("0");
}

inline void F5() { // flash
    int i;
    Rep (i,1,m) f(poi[i]) += f(poi[i]^1), f(poi[i]^1) = 0;
}

inline void ans4() {
    int last, now, rec;
    F5();
    Each(it,ans4_0) f(poi[*it]) = 0;
    S = 1, T = n;
    last = SAP(); F5();
    Each(it,ans4_1) {
        if (last == 0) break;
        rec = f(poi[*it]), f(poi[*it]) = 0;
        now = SAP(); F5();
        if (now == last) f(poi[*it]) = rec;
        else last = now, ans4_0.push_back(*it);
    }
    std::sort(ans4_0.begin(), ans4_0.end());
    Each(it,ans4_0) printf("%d ", *it);
    puts("");
}

int main() {
    freopen("JJandLazy.in" ,"r",stdin ) ;
    freopen("JJandLazy.out","w",stdout) ;
    int i, ans3, q, ope;
    r(n), r(m);
    N = n, S = 1, T = n;
    Rep (i,1,m) {
        r(x[i]), r(y[i]), r(q);
        poi[i] = te+1, Add(x[i],y[i],q);
    }
    ans3 = SAP(); /// ans3
    Judge();      /// ans2 & select edges for ans4
    for (r(q); q; q -- )
        if (r(ope), r(i), ope == 1) ans1(i); /// ans1
        else printf("%d\n", ans2[i]);        /// ans2
    printf("%d\n", ans3);
    ans4();       /// ans4
    fclose(stdin), fclose(stdout);
    return 0 ;
}