HDU3715 2-SAT

最新推荐文章于 2017-10-13 16:04:59 发布

ACder_chen

最新推荐文章于 2017-10-13 16:04:59 发布

阅读量578

点赞数

分类专栏：图论文章标签： 2-SAT

图论专栏收录该内容

8 篇文章

订阅专栏

本文探讨了一种解决复杂网络流匹配问题的高效算法。通过详细分析网络流匹配的基本原理，提出了一种改进的算法，该算法在保持高效率的同时，能够准确地解决各种规模的网络流匹配问题。实验结果显示，该算法相较于现有方法，在处理大规模网络流匹配任务时表现出显著的性能提升。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

const int M = 20005;
int dfn[M];
int low[M];
int ins[M];
int sccf[M];
int a[M];
int b[M];
int c[M];
vector<int>que[M];
stack<int>s;
int index, scc;
int n, m;
int ans;



void init() {

    index = 1;
    scc = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(ins, 0, sizeof(ins));
    memset(sccf, 0, sizeof(sccf));
    for(int i = 0; i <= n*2; i++)
        que[i].clear();
    while(!s.empty())
        s.pop();
}

/*
假设a = 0 则 a‘ = 1， b = 0 则 b’ = 1；
将a b 定义一种值， 则相应的值都将确定，如果这种情况可以满足题目要求， 这此题与解，因为题目中的数值
都是相对的。

如果 C = 0 , 则 a 和b 矛盾， 则a -> b' b ->a'
如果 c = 1 则  a 和b' b 和a'矛盾 则 a -> b b' ->a' b ->a a' ->b'
如果 c = 2 则  a‘ 和 b'矛盾， 则 a'->b b'->a

*/
void build_map(int mid) {

    for(int i = 1; i <= mid; i++) {

        if(c[i] == 0) {

            que[a[i]].push_back(b[i] + n);
            que[b[i]].push_back(a[i] + n);
        }else if(c[i] == 1) {

            que[a[i]].push_back(b[i]);
            que[b[i] + n].push_back(a[i] + n);
            que[b[i]].push_back(a[i]);
            que[a[i] + n].push_back(b[i] + n);

        }else {

            que[a[i] + n].push_back(b[i]);
            que[b[i]+n].push_back(a[i]);
        }
    }
}

void Tarjan(int u) {

    int v;
    dfn[u] = low[u] = index++;
    ins[u] = 1;
    s.push(u);

    for(int i = 0; i <(int)que[u].size(); i++) {

        v = que[u][i];
        if(!dfn[v]) {

            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(ins[v]) {

            low[u] = min(low[u], low[v]);
        }
    }
    if(dfn[u] == low[u]) {

        scc++;
        do {

            v = s.top();
            s.pop();
            ins[v] = 0;
            sccf[v] = scc;
        }while(u != v);
    }
}

bool judge(int mid) {

     init();
   build_map(mid);

    for(int i = 0; i <2*n; i++) {

        if(!dfn[i])
            Tarjan(i);
    }
    for(int i = 0; i < n; i++)
        if(sccf[i] == sccf[i + n]){
           return false;
        }
    return true;
}

void work() {

    int l = 0, r = m;
    ans = 0;

    while(l <= r) {

        int mid = (l + r)/2;

        if(judge(mid)) {

          ans = mid;
            l = mid+1;

        }else {

            r = mid -1;
        }

    }
    printf("%d\n", ans);
}

int main()
{
    int t;
    scanf("%d", &t);

    while(t--){

        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; i++)
           scanf("%d%d%d", &a[i], &b[i], &c[i]);
       // printf("ddd\n");
        work();
    }

    return 0;
}