社区讨论

萌新刚学网络流,求助

P1402酒店之王参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi7ruwrt
此快照首次捕获于
2025/11/21 02:35
4 个月前
此快照最后确认于
2025/11/21 02:35
4 个月前
查看原帖
P1402 酒店之王 用的标准的dinic算法,跑模板只用了200+ms,相似的题也就几ms,但这个题莫名TLE8个点,有dalao帮帮我吗?
CPP
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define oo 0x3f3f3f3f
#define ri register int
#define iv inline void
typedef long long ll;
int n,p,q,s,t,timer,tot = -1,head[4100],dis[4100];
bool vis[4100];
struct Edge{
	int to,w,next;
}e[8100];

template<class T>
inline void read(T &res){
	static char ch;T flag = 1;
	while( ( ch = getchar() ) < '0' || ch > '9' )
	  if( ch == '-' ) flag = -1;
	res = ch - 48;
	while( ( ch = getchar() ) >= '0' && ch <= '9' )
	  res = res * 10 + ch - 48;
	res *= flag;
}

inline int min( int x , int y ){
	return x < y ? x : y;
}

iv add( int from , int to , int w ){
	e[ ++tot ].to = to;
	e[ tot ].next = head[ from ];
	e[ tot ].w = w;
	head[ from ] = tot;
}

int dfs( int x , int lim ){
	if( x == t ) return lim;
	int ans = 0;
	for( ri i = head[ x ] ; i != -1 ; i = e[ i ].next )
	  if( e[ i ].w && dis[ e[ i ].to ] == dis[ x ] + 1 ){
	  	  int y = dfs( e[ i ].to , min( e[ i ].w , lim ) );
	  	  if( y ){
	  	  	  e[ i ].w -= y;e[ i^1 ].w += y;
	  	  	  ans += y;lim -= y;
	  	  	  if( !lim ) return ans;
	  	  }
	  }
	return ans;
}

inline bool bfs(){
	timer++;
	queue<int> q;
	dis[ s ] = 0;vis[ s ] = timer;
	q.push( s );
	while( !q.empty() ){
		int x = q.front();q.pop();
		for( ri i = head[ x ] ; i != -1 ; i = e[ i ].next ){
			int v = e[ i ].to;
			if( e[ i ].w == 0 ) continue;
			if( vis[ v ] != timer ){
				vis[ v ] = timer;
				dis[ v ] = dis[ x ] + 1;
				q.push( v ); 
			}
		}
	}
	return vis[ t ] == timer;
}

inline int dinic(){
	int ans = 0;
	while( bfs() ) ans += dfs( s , 0x3f3f3f3f );
	return ans;
}

int main()
{
	memset( head , -1 , sizeof( head ) );
    read( n );read( p );read( q );
    s = 1;t = p + q + n + n + 2;
    for( ri i = 2 ; i <= p + 1 ; i++ ){
    	add( 1 , i , 1 );
    	add( i , 1 , 0 );
    }//源点和房 
    for( ri i = p + 2 ; i <= p + n + 1 ; i++ ){
    	add( i , i + n , 1 );
    	add( i + n , i , 0 );
    }//被拆开的人 
    for( ri i = p + n + n + 2 ; i <= p + q + n + n + 1 ; i++ ){
    	add( i , p + q + n + n + 2 , 1 );
    	add( p + q + n + n + 2 , i , 0 );
    }//菜和汇点
	for( ri i = p + 2 ; i <= p + n + 1 ; i++ )
	  for( ri j = 2 ; j <= p + 1 ; j++ ){
	  	  int x;read( x );
	  	  if( x ){
	  	  	  add( j , i , 1 );
	  	  	  add( i , j , 0 );
	  	  }
	  }
	for( ri i = p + n + 2 ; i <= p + n + n + 1 ; i++ )
	  for( ri j = p + n + n + 2 ; j <= p + q + n + n + 1 ; j++ ){
	  	  int x;read( x );
	  	  if( x ){
	  	  	  add( i , j , 1 );
	  	  	  add( j , i , 0 );
	  	  }
	  }
	printf( "%d\n" , dinic() );
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...