社区讨论

萌新写了个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 条回复,欢迎继续交流。

正在加载回复...