這道題的數(shù)據(jù)（至少我們oj的）有問題！按照我下面的做法能夠過數(shù)據(jù)，但并不是正解。（我在代碼后面說一下這數(shù)據(jù)錯(cuò)哪里了。。）
二分圖即可，也沒必要拆點(diǎn)，其實(shí)只是把點(diǎn)視為兩排，在左邊一排向右邊能連邊的點(diǎn)連邊（說白了就是左邊點(diǎn)能放右邊點(diǎn)后面），之后把右邊點(diǎn)的link設(shè)為左邊點(diǎn)。就這樣。?？荚嚂r(shí)以為是dp,最后交了深搜。。。

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n, ans=0, idc=0; int a[305][305],vis[305],l[305]; struct Book{int x, y;}book[305]; //inline bool cmp(Book x,Book y){return x.x==y.x?x.y>y.y:x.x>y.y;} inline int find(int x) {for(int i=1;i<=n;i++)if(!vis[i]&&a[x][i]){vis[i]=1;if(!l[i]||find(l[i])){l[i]=x;return 1;}}return 0; } int main(){// freopen ("militarytraining.in", "r", stdin);// freopen ("militarytraining.out", "w", stdout);scanf("%d", &n);for(int i=1; i<=n; i++)scanf("%d%d", &book[i].x, &book[i].y);//sort(book+1, book+n+1,cmp);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j&&book[i].y>=book[j].y&&book[i].x>=book[j].x)a[j][i]=1;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));ans+=find(i);}printf("%d\n", n-ans); }

二分圖只能處理無DAG的情況，若存在DAG，對于這道題也就是完全相等的書之間可以互相放，但這種環(huán)會形成把1放在2后，并且2在1后面的靈異現(xiàn)象。說白了就是不對。所以要么拆成2×n個(gè)點(diǎn)，或者縮掉所有相等的點(diǎn)。呵呵。。。。

轉(zhuǎn)載于:https://www.cnblogs.com/QTY2001/p/7632661.html

總結(jié)

以上是生活随笔為你收集整理的二分图 crf的军训的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。