本文主要是介绍【HDU】3729 I'm Telling the Truth 离散+最大流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】3729 I'm Telling the Truth
题目分析：我看这么大的数据范围，如果普通二分肯定要超时的啊。。。然后就敲了一个离散化+最大流了。。。
但是我网上看他们的题解，都是裸裸的开一个100万的数组啊！！！还比我离散的网络流还快啊啊啊！！于是我就测一次给的区间有多大（如果超出一定范围就拿一个变量除以0让报RE），第一次10000没事，然后1000。。还是没事。。。然后100仍旧没事。。我都怀疑是不是不报RE了。。。。火了，5！还是没事。。。。不管了直接1，终于给我报RE了！！！！！！最后的测验结果是：每次给的区间范围不超过5！！！！！
我不多说。。数据真是弱。。。
网络流就离散化区间就好了，很简单的。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )
#define copy( a , x ) memcpy ( a , x , sizeof a )const int MAXN = 60 + 120 + 2 ;
const int MAXE = 14400 + 5 ;
const int MAXQ = 200 ;
const int INF = 0x3f3f3f3f ;struct Edge {int v , c , n ;Edge () {}Edge ( int var , int cost , int next ) :v ( var ) , c ( cost ) , n ( next ) {}
} ;struct Node {int l , r ;void input () {scanf ( "%d%d" , &l , &r ) ;}
} ;struct NetWork {Edge E[MAXE] ;int H[MAXN] , cntE ;int d[MAXN] , num[MAXN] , cur[MAXN] , pre[MAXN] ;int Q[MAXQ] , head , tail ;int s , t , nv ;int n , m ;int flow ;//-------------int a[MAXN] ;Node A[MAXN] ;//-------------void init () {cntE = 0 ;clear ( H , -1 ) ;}void addedge ( int u , int v , int c ) {E[cntE] = Edge ( v , c , H[u] ) ;H[u] = cntE ++ ;E[cntE] = Edge ( u , 0 , H[v] ) ;H[v] = cntE ++ ;}void rev_bfs () {head = tail = 0 ;clear ( d , -1 ) ;clear ( num , 0 ) ;Q[tail ++] = t ;d[t] = 0 ;num[d[t]] = 1 ;while ( head != tail ) {int u = Q[head ++] ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( ~d[v] )continue ;d[v] = d[u] + 1 ;num[d[v]] ++ ;Q[tail ++] = v ;}}}int ISAP () {copy ( cur , H ) ;rev_bfs () ;int u = pre[s] = s , i ;while ( d[s] < nv ) {if ( u == t ) {int f = INF , pos ;for ( i = s ; i != t ; i = E[cur[i]].v )if ( f > E[cur[i]].c ) {f = E[cur[i]].c ;pos = i ;}for ( i = s ; i != t ; i = E[cur[i]].v ) {E[cur[i]].c -= f ;E[cur[i] ^ 1].c += f ;}u = pos ;flow += f ;}for ( i = cur[u] ; ~i ; i = E[i].n )if ( E[i].c && d[u] == d[E[i].v] + 1 )break ;if ( ~i ) {cur[u] = i ;pre[E[i].v] = u ;u = E[i].v ;}else {if ( 0 == ( -- num[d[u]] ) )break ;int mmin = nv ;for ( i = H[u] ; ~i ; i = E[i].n )if ( E[i].c && mmin > d[E[i].v] ) {mmin = d[E[i].v] ;cur[u] = i ;}d[u] = mmin + 1 ;num[d[u]] ++ ;u = pre[u] ;}}return flow ;}int unique ( int a[] , int n ) {int cnt = 1 ;sort ( a + 1 , a + n + 1 ) ;REPF ( i , 2 , n )if ( a[i] != a[cnt] )a[++ cnt] = a[i] ;return cnt ;}int binary_search ( int x , int l , int r ) {while ( l < r ) {int m = ( l + r ) >> 1 ;if ( a[m] >= x )r = m ;elsel = m + 1 ;}return l ;}void input () {m = 0 ;scanf ( "%d" , &n ) ;REPF ( i , 1 , n ) {A[i].input () ;a[++ m] = A[i].l ;a[++ m] = ++ A[i].r ;//[ , ]转化为[ , )}m = unique ( a , m ) ;}void build () {REPF ( i , 2 , m ) {addedge ( n + i , t , a[i] - a[i - 1] ) ;REPF ( j , 1 , n )if ( A[j].l <= a[i - 1] && a[i] <= A[j].r )addedge ( j , n + i , 1 ) ;}}void solve () {init () ;input () ;s = 0 ;t = m + n + 1 ;nv = t + 1 ;build () ;int cnt = cntE ;flow = 0 ;REPV ( i , n , 1 ) {addedge ( s , i , 1 ) ;ISAP () ;}printf ( "%d\n" , flow ) ;int flag = 0 ;for ( int i = H[0] ; ~i ; i = E[i].n ) {if ( !E[i].c ) {if ( flag )printf ( " " ) ;flag = 1 ;printf ( "%d" , E[i].v ) ;}}printf ( "\n" ) ;}
} ;NetWork nw ;int main () {int T ;scanf ( "%d" , &T ) ;while ( T -- )nw.solve () ;return 0 ;
}这篇关于【HDU】3729 I'm Telling the Truth 离散+最大流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
