description

題目描述
小豆報(bào)名參加智力競(jìng)賽，他帶上了 n個(gè)好朋友作為親友團(tuán)一塊來參加比賽。
比賽規(guī)則如下：一共有 m道題目，每個(gè)人都有 1 次答題機(jī)會(huì)，每次答題為選擇一道題目回答，在回答正確后，可以從這個(gè)題目的后續(xù)題目，直到題目答錯(cuò)題目或者沒有后續(xù)題目。
每個(gè)問題都會(huì)代表一個(gè)價(jià)值，比賽最后的參賽選手獲得獎(jiǎng)勵(lì)價(jià)值等價(jià)于該選手和他的親友團(tuán)沒有回答的問題中的最低價(jià)值。
我們現(xiàn)在知道小豆和他的親友團(tuán)實(shí)力非常強(qiáng)，能夠做出這次競(jìng)賽中的所有題目。
小豆想知道在知道題目和后續(xù)題目的條件下，他最大能獲得價(jià)值是多少?

輸入格式
第一行有兩個(gè)整數(shù) n, m
接下來 m行，第 i+1 行表示編號(hào)為 i的題目的題目信息;
格式如下 vi,ki,ai,1,ai,2,…,ai,ki
其中 vi表示該題目的價(jià)值， ki 表示這個(gè)題目的后續(xù)， ai,1,ai,2,…,ai,ki 表示這 i個(gè)題目的后續(xù)題目編號(hào)。

輸出格式
如果全部題目都能答對(duì)，則輸出 AK ，否則輸出小豆可以獲得的最高獎(jiǎng)勵(lì)價(jià)值。

樣例
樣例輸入 1

1 3 1 0 2 1 3 3 0AK

樣例輸入 2

1 6 1 2 2 3 2 1 4 3 1 4 4 1 6 5 0 6 05

數(shù)據(jù)范圍與提示
對(duì)于 10%的數(shù)據(jù)， 1≤n,m≤10 。
對(duì)于 20% 的數(shù)據(jù)， 1≤n,m≤100 。
對(duì)于 100% 的數(shù)據(jù)， 1≤n≤50,1≤m≤500,vi≤109,ki,ai,j≤m

solution

說實(shí)話沒讀懂題面

一句話題意：給出一個(gè)帶權(quán)有向圖，選出$n+1$條鏈
能否全部點(diǎn)覆蓋，如果不能，不能覆蓋的點(diǎn)權(quán)最小值最大是多少

最小值最大，套路又整二分上
考慮二分不能覆蓋的最小值
就轉(zhuǎn)化為了$DAG$的最小不相交路徑覆蓋條數(shù)
也就可以轉(zhuǎn)化為二分圖最大匹配，最大匹配數(shù)就是可合并的路徑條數(shù)
點(diǎn)數(shù)?最大匹配數(shù)＝最小不相交路徑覆蓋數(shù)

如果二分結(jié)果大于最大值，就說明每道題都能被覆蓋到，就$AK$了

code

#include <cstdio> #include <vector> #include <cstring> using namespace std; #define maxn 505 vector < int > G[maxn]; int n, m; int val[maxn], match[maxn]; int g[maxn][maxn], f[maxn][maxn]; bool vis[maxn];bool find( int u ) {for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if( vis[v] ) continue;vis[v] = 1;if( ! match[v] || find( match[v] ) ) {match[v] = u;return 1;}}return 0; }bool check( int x ) {memset( match, 0, sizeof( match ) );for( int i = 1;i <= m;i ++ ) G[i].clear();memset( f, 0, sizeof( f ) );for( int i = 1;i <= m;i ++ )for( int j = 1;j <= m;j ++ )if( val[i] <= x && val[j] <= x )f[i][j] = g[i][j];for( int k = 1;k <= m;k ++ )for( int i = 1;i <= m;i ++ )if( f[i][k] )for( int j = 1;j <= m;j ++ )f[i][j] |= f[i][k] & f[k][j];int tot = 0;for( int i = 1;i <= m;i ++ ) {if( val[i] > x ) continue;tot ++;for( int j = 1;j <= m;j ++ )if( f[i][j] ) G[i].push_back( j );}for( int i = 1;i <= m;i ++ ) {if( val[i] > x ) continue;memset( vis, 0, sizeof( vis ) );if( find( i ) ) tot --;}return tot <= n; }int main() {scanf( "%d %d", &n, &m );n ++;int l = 1e9, r = 0;for( int i = 1, c, x;i <= m;i ++ ) {scanf( "%d %d", &val[i], &c );l = min( l, val[i] ), r = max( r, val[i] );while( c -- ) scanf( "%d", &x ), g[i][x] = 1;}for( int k = 1;k <= m;k ++ )for( int i = 1;i <= m;i ++ )if( g[i][k] ) //不加此優(yōu)化 時(shí)間復(fù)雜度就會(huì)跑滿m^3log for( int j = 1;j <= m;j ++ )g[i][j] |= g[i][k] & g[k][j];int maxx = r;while( l <= r ) {int mid = ( l + r ) >> 1;if( check( mid ) ) l = mid + 1;else r = mid - 1;}if( l > maxx ) printf( "AK\n" );else printf( "%d\n", l );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[TJOI2018]智力竞赛 （匈牙利）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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