[HZOI 2016]颓废元 - ztx - 366884

记录编号	366884	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]颓废元	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2017-01-26 12:23:01	内存使用	0.44 MiB
显示代码纯文本
/***
 * ans1 ope 1 x边是否一定在最大流的边集中，重设x边两端点为S,T推流是否能推尽
 * ans2 ope 2 x边是否在所有最小割边集中，残量网络 dfs求S,T点集，x边两侧属于不同点集则在所有最小割边集中
 * ans3 最大流
 * ans4 字典序最小的最小割边集：
 * 从小到大枚举割边，并计算没有这条边的最大流，如最大流减少，则删去此边，记下此时的最大流，答案中加上此边；否则，不删边，枚举下一条边；直到最后最大流变为0.
 *
 */

#include <bits/stdc++.h>

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 rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
#define  maxN  410LL
#define  maxM  4010LL
#define  infi  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)

int e[3][maxM<<1], star[maxN] , tote = 1;
inline void AddEdge(int u, int v, int cap) {
    tote ++ , t(tote) = v, f(tote) = cap, n(tote) = s(u), s(u) = tote;
    tote ++ , t(tote) = u, f(tote) = 0, n(tote) = s(v), s(v) = tote;
}

#define  min(x,y) ((x)<(y)?(x):(y))
int N, S, T, h[maxN], vh[maxN];

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

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,infi);
    return ret;
}

int vis[maxN] = {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;
int x[maxM], y[maxM], poi[maxM];
bool ans2[maxM] = {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])) //  modify 01
            ans4_1.push_back(i);
    }
// puts("printing   ans4_0");
// for (it = ans4_0.begin(); it != ans4_0.end(); it ++ )
//     printf("%d ", *it);
// puts("printing   ans4_1");
// for (it = ans4_1.begin(); it != ans4_1.end(); it ++ )
//     printf("%d ", *it);
// puts("\nendit-----------");
}

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"); return;}
    if (!vis[u] && !vis[v]) puts("1");
    else puts("0");


    return;

// printf("answering %d: ", i);
    if (f(poi[i]^1) == 0) { puts("0"); return; }
    int rec1 = f(poi[i]), rec2 = f(poi[i]^1), rflow = 0;
    f(poi[i]) = f(poi[i]^1) = 0;
    S = x[i], T = y[i];
    memset(vh, 0, sizeof vh);
    memset(h, 0, sizeof h);
    vh[S] = N;
    while (h[S]<N && rflow<rec2) rflow += dfs(S,rec2-rflow);
    f(poi[i]) = rec1+rflow, f(poi[i]^1) = rec2-rflow;
// printf(" ==================> rflow = %d rec2 = %d\n", rflow, rec2);
    printf("%d\n", rflow!=rec2);
}

inline void F5() {
    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();
    for (it = ans4_0.begin(); it != ans4_0.end(); it ++ )
        f(poi[*it]) = 0;
    S = 1, T = n;
    last = SAP(); F5();
    for (it = ans4_1.begin(); it != ans4_1.end(); it ++ ) {
        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());
    for (it = ans4_0.begin(); it != ans4_0.end(); it ++ )
        printf("%d ", *it);
}

inline void Print() {
puts("printing ===============");
    for (int i = 2; i < tote; i += 2) {
        printf("%d  ->  %d :  %d  %d \n", t(i+1), t(i), f(i), f(i+1));
    }
puts("end printing ===========");
}


int main() {
  #define READ
    #ifdef  READ
        freopen("JJandLazy.in" ,"r",stdin ) ;
        freopen("JJandLazy.out","w",stdout) ;
    #endif
    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] = tote+1;
        AddEdge(x[i],y[i],q);
    }
    ans3 = SAP(); // t3
// Print();
    Judge();  // t2 & select edges for ans4
    for (r(q); q; q -- ) {
        r(ope), r(i);
        if (ope == 1) 
// Print(),
            ans1(i);
        //if (ope == 2) printf("%d\n", ans2[i]);

        else printf("%d\n", ans2[i]);
    }
    printf("%d\n", ans3);
// puts("ans4-------------");
    ans4();
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}

/*
7
7
1 2 10
2 3 1
3 4 1
4 7 10
1 5 10
5 6 1
6 7 10
5
1 2
1 3
1 6
2 6
2 2


you 0 you 1
*/