P1525 关押罪犯

用二分图写的， 样例和第一个点过了，其他全WA了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls id << 1
#define rs id << 1 | 1
#define inf 0x3f3f3f3f
typedef pair <int,int> pii;
const int MAXN = 1e5 + 10;
int n,m,a[MAXN],b[MAXN],c[MAXN],head[MAXN],cnt,maxn = -inf,ans,color[MAXN];
bool flag;
struct Node
{
    int u,v,w,nxt;
}e[MAXN << 1];
void add(int u,int v,int w){e[++cnt] = {u,v,w,head[u]};head[u] = cnt;}
inline void dfs(int u,int col)
{
    if(!flag) return; 
    color[u] = col;
    for(int i = head[u]; ~ i;i = e[i].nxt)
    {
        int now = e[i].v;
        if(!color[now]) dfs(now,col ^ 1);
        else if(color[now] == col) flag = false;
    }
}
bool check(int k)
{
    memset(head,-1,sizeof head);
    memset(color,0,sizeof color);
    while(cnt) e[cnt].u = e[cnt].v = e[cnt].w = e[cnt].nxt = 0,cnt--;
    for(int i = 1;i <= n;i++) if(c[i] > k) add(a[i],b[i],c[i]);
    flag = true;
    for(int i = 1;i <= n;i++) if(!color[i]) dfs(i,0);
    return flag;
}
signed main() 
{
    memset(head,-1,sizeof head);
    cin >> n >> m;
    for(int i = 1;i <= m;i++) cin >> a[i] >> b[i] >> c[i],maxn = max(c[i],maxn);
    int l = 0,r = maxn + 1;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(check(mid)) ans = mid,r = mid - 1;
        else l = mid + 1;
    }
    if(m == 1) cout << "0";
    else cout << ans << endl; 
    return 0;
}