社区讨论
萌新刚学网络流,求助
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 条回复,欢迎继续交流。
正在加载回复...