社区讨论
萌新写了个Dinic写挂了,求dalao差错QAQ
P1361小M的作物参与者 4已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @mi7x3goj
- 此快照首次捕获于
- 2025/11/21 05:02 4 个月前
- 此快照最后确认于
- 2025/11/21 06:36 4 个月前
bfs就一直在返回True,求大佬看看哪里挂了qwq
CPP#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <queue>
const int N = 1e4 + 10;
const int INF = 10000001;
int n , t = 1 , sum , m;
int head[N] , dep[N] , cur[N];
struct Edge {
int date;
int to;
int next;
}e[N << 3];
int tmp[1005];
std :: queue < int > qu;
inline void add ( int x , int y , int z ) {
e[++t].to = y;
e[t].date = z;
e[t].next = head[x];
head[x] = t;
return;
}
inline bool bfs ( int s , int t ) {
memset ( dep , 0x3f3f3f3f , sizeof ( dep ) );
while ( !qu.empty () )
qu.pop ();
for ( int i = 1 ; i <= n ; i++ )
cur[i] = head[i];
qu.push ( s );
dep[s] = 0;
while ( !qu.empty () ) {
int j = qu.front ();
qu.pop ();
for ( int i = head[j] ; i ; i = e[i].next ) {
int k = e[i].to;
if ( dep[k] > INF && e[i].date ) {
dep[k] = dep[j] + 1;
qu.push ( k );
}
}
}
if ( dep[t] < INF )
return true;
else
return false;
}
#define max(a,b) (a>b)?a:b
#define min(a,b) (a<b)?a:b
int Dinic ( int root , int t , int limit ) {
if ( root == t || !limit )
return limit;
int f , flow = 0;
for ( int i = cur[root] ; i ; i = e[i].next ) {
int j = e[i].to;
cur[root] = i;
if ( dep[j] == dep[root] + 1 && ( f = Dinic ( j , t , min ( e[i].date , limit ) ) ) ) {
flow += f;
limit -= f;
e[i].date -= f;
e[i ^ 1].date += f;
if ( !limit )
break;
}
}
return flow;
}
inline int Work () {
int MaxFlow = 0;
while ( bfs ( 0 , n + 1 ) )
MaxFlow += Dinic ( 0 , n + 1 , INF );
return MaxFlow;
}
int main ( void ) {
scanf ( "%d" , &n );
for ( int i = 1 ; i <= n ; i++ ) {
int x;
scanf ( "%d" , &x );
add ( 0 , i , x );
add ( i , 0 , 0 );
sum += x;
}
for ( int i = 1 ; i <= n ; i++ ) {
int x;
scanf ( "%d" , &x );
add ( i , n + 1 , x );
add ( n + 1 , i , 0 );
sum += x;
}
int Addition = 1;
scanf ( "%d" , &m );
for ( int i = 1 ; i <= m ; i++ ) {
int num , c1 , c2;
memset ( tmp , 0 , sizeof ( tmp ) );
scanf ( "%d" , &num );
Addition++;
scanf ( "%d%d" , &c1 , &c2 );
sum += ( c1 + c2 );
add ( 0 , n + Addition , c1 );
add ( n + Addition , 0 , 0 );
for ( int j = 1 ; j <= num ; j++ ) {
scanf ( "%d" , &tmp[j] );
add ( n + Addition , tmp[j] , INF );
add ( tmp[j] , n + Addition , 0 );
}
Addition++;
add ( n + Addition , n + 1 , c2 );
add ( n + 1 , n + Addition , 0 );
for ( int j = 1 ; j <= num ; j++ ) {
add ( tmp[j] , n + Addition , INF );
add ( Addition + n , tmp[j] , 0 );
}
}
printf ( "%d\n" , sum - Work () );
system ( "pause" );
return 0;
}
回复
共 15 条回复,欢迎继续交流。
正在加载回复...