URAL 1949 The Best Picture in the Galaxy 二分匹配 求字典序最小解
題目鏈接：點擊打開鏈接 點擊打開鏈接
題意：
給定n部電影k個學生
下面n行給出每部電影的開映時間，結束時間，女演員的個數。
若一個學生看了一部電影，接下來想看另一部電影必須滿足：
1、兩部電影時間不能重合，即後面那部的開映時間>=前面那部的結束時間
2、女演員數量不能比之前看的少
問：
k個學生最多能看多少部電影。
以二進制輸出。
若有多種方案輸出字典序最小解
思路：
二分匹配，就是最小路徑覆蓋吧。。
把電影拆成2個點作為x集和y集。
1、首先我們加入一部電影，若這部電影能插入原先的圖，則直接插入（插入的意思就是在原圖上根據關系邊把點連接到原圖的某個聯通塊上）
2、若無法插入則判斷是否有空閒的學生，強行看這部電影（即在原圖中加入一個孤立點）
3、若沒有空閒的學生就不加入這部電影（即再把這個點刪掉）
#include
#include
#include
#include
#include
using namespace std;
#define ll int
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define N 105
int lef[N], del[N];//lef[v]表示Y集的點v 當前連接的點 , pn為x點集的點數
bool T[N]; //T[u] 表示Y集 u 是否已連接X集
vectorG[N]; //匹配邊 G[X集].push_back(Y集) 注意G 初始化
bool match(int x){ // x和Y集 匹配 返回x點是否匹配成功
for(int i=0; i k)
{
del[i] = true; delnum++;
yes = false;
}
printf("%d", yes);
}
puts("");
}
return 0;
}
/*
4 1
1 2 1
2 3 2
3 4 3
4 5 4
4 2
1 3 1
2 3 2
3 4 3
4 5 4
4 1
1 3 1
2 3 2
3 4 3
4 5 4
4 1
1 3 1
2 3 4
3 4 3
4 5 4
4 2
1 3 1
2 3 4
3 4 3
4 5 4
2 1
0 1000 1
0 1000 2
2 2
0 1000 1
0 1000 2
3 2
1 10 6
2 11 5
3 12 4
*/
