这道题做了一个多月？感谢噶爷教我做题
（滑稽）自己给自己停bc准备中考然而还是考的不咋地
这道题二分之后就是找最小链覆盖，算经典的吧。
注意下那个权可能重复啊，二分要离散化。。（然而我WA无数次的原因居然是打了个match[y]==false什么鬼）
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int n,peo; int c[510];bool mp[510][510]; struct node { int x,y,next; }a[310000];int len,last[510]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } bool chw[510]; int match[510]; bool findmuniu(int x) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(chw[y]==false) { chw[y]=true; if(match[y]==0||findmuniu(match[y])==true) { match[y]=x; return true; } } } return false; } bool check(int d) { if(d==0)return true; int tot=0; for(int i=1;i<=n;i++) if(c[i]<=d)tot++; //DAG最小链覆盖 len=0;memset(last,0,sizeof(last)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(c[i]<=d&c[j]<=d) if(mp[i][j]==true)ins(i,j); int sum=0; memset(match,0,sizeof(match)); for(int i=1;i<=n;i++) { memset(chw,false,sizeof(chw)); if(findmuniu(i)==true)sum++; } return ((tot-sum)>peo)?(false):(true); } int erc[510]; int main() { scanf("%d%d",&peo,&n);peo++; memset(mp,false,sizeof(mp)); for(int i=1;i<=n;i++) { scanf("%d",&c[i]), erc[i]=c[i]; int m,k; scanf("%d",&m); for(int j=1;j<=m;j++) scanf("%d",&k), mp[i][k]=true; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(k!=i) for(int j=1;j<=n;j++) if(k!=j&&i!=j)mp[i][j]|=(mp[i][k]&mp[k][j]); erc[0]=0; sort(erc+1,erc+n+1); n=unique(erc+1,erc+n+1)-erc-1; erc[n+1]=-1; //LSH int l=0,r=n,ans; while(l<=r) { int mid=(l+r)/2; if(check(erc[mid])==true) { l=mid+1; ans=erc[mid+1]; } else r=mid-1; } if(ans==-1)printf("AK "); else printf("%d ",ans); return 0; }