HDU - 3729 I'm Telling the Truth（二分匹配）

题意：有n个人，每个人给出自己的名次区间，问最多有多少个人没撒谎，如果有多解，输出字典序最大的解。

分析：

1、因为字典序最大，所以从后往前分析。

2、假设后面的人没说谎，并将此作为已知条件，然后从后往前依次给每个人找到合适的名次，输出所有能找到合适名次的人即可。

3、假定给第i个人安排名次，第i+1~n个人名次已经安排好，假如第i个人想占的名次被第j个人所占，那就从第j个人可以占的名次中再找个合适的名次给j，然后把空出来的这个名次给i，如果i可以占的所有名次都被占且占领的人找不到其他可以占的名次，则i找不到合适的名次。

4、总而言之，从后往前，依次给每个人匹配一个名次，若匹配不到（出现矛盾），则该人说谎。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 10;

const double pi = acos(-1.0);

const int MAXN = 60 + 10;

const int MAXT = 100000 + 10;

using namespace std;

bool used[MAXT];

int match[MAXT];

int n;

vector<int> ans;

struct Node{

    int l, r;

    void read(){

        scanf("%d%d", &l, &r);

    }

}num[MAXN];

bool dfs(int x){

    for(int i = num[x].l; i <= num[x].r; ++i){

        if(!used[i]){

            used[i] = true;

            if(match[i] == -1 || dfs(match[i])){

                match[i] = x;

                return true;

            }

        }

    }

    return false;

}

void hungary(){

    for(int i = n; i >= 1; --i){

        memset(used, false, sizeof used);

        if(dfs(i)) ans.push_back(i);

    }

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        ans.clear();

        memset(match, -1, sizeof match);

        scanf("%d", &n);

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

            num[i].read();

        }

        hungary();

        int len = ans.size();

        printf("%d\n", len);

        for(int i = len - 1; i >= 0; --i){

            if(i != len - 1) printf(" ");

            printf("%d", ans[i]);

        }

        printf("\n");

    }

    return 0;

}

巴特西

HDU - 3729 I'm Telling the Truth（二分匹配）

最新文章

热门文章