社区讨论

求助,8TLE,不知道哪里错了。。。。

P1361小M的作物参与者 8已保存回复 9

讨论操作

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

当前回复
9 条
当前快照
1 份
快照标识符
@mi7ussdp
此快照首次捕获于
2025/11/21 03:58
4 个月前
此快照最后确认于
2025/11/21 03:58
4 个月前
查看原帖
求助大神,麻烦看一下是不是写错了。
CPP
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxN = 10005;
const int maxM = 4000005;
const int inf = 1e9;

int n , m, s, t;

inline int gi() {
  int x = 0,f = 1;char c = getchar();
  while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
  while(c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
  return x * f;	
} 

struct Node {
  int v,w,nex;
}Map[maxM];
int head[maxN] , dep[maxN], num = -1;

void add_Node(int u , int v, int w) {
	Map[++ num] = (Node) {v , w, head[u]};head[u] = num;
	Map[++ num] = (Node) {u , 0, head[v]};head[v] = num;
}

int sum;

namespace Din{
	bool bfs() {
	  queue<int>q;
	  memset(dep,0,sizeof(dep));
	  dep[s] = 1;
	  q.push(s);
	  do{
	    int u = q.front();
	    q.pop();
	    for(register int i = head[u];i != -1;i = Map[i].nex) {
	      int v = Map[i].v;
	      if(Map[i].w && dep[v] == 0) {
	        dep[v] = dep[u] + 1;
	        q.push(v);
	      }
	    }
	  }while(!q.empty());
	  return dep[t];
	}
	
	int dfs(int now,int dist) {
	  if(now == t)return dist;
	  int nowflow = 0;
	  for(register int i = head[now] ;i != -1;i = Map[i].nex) {
	    int v = Map[i].v;
	      if(dep[v] == dep[now] + 1 && Map[i].w) {
	        int di = dfs(v,min(dist,Map[i].w));
	        Map[i].w -= di;
	        Map[i ^ 1].w += di;
	        nowflow += di;
	        dist -= di;
	        if(!dist) break;
	      }
	  }
	  return nowflow;
	}
	
	inline void Dinic() {
	  int Ans = 0;
	  while(bfs()) {
	    while(int d = dfs(s,inf))
	      Ans += d;
	  }
	  printf("%d",sum - Ans);
	  return;
	}
}

inline void init() {
	s = 0;
	t = s + 1;
	memset(head , -1, sizeof(head));
}

int main() {
	n = gi();	
	init();
	for(register int i = 1;i <= n;++ i) {int w = gi();add_Node(s , i + 1, w);sum += w;}
	for(register int i = 1;i <= n;++ i) {int w = gi();add_Node(i + 1 , t, w);sum += w;}
	m = gi();
	int cnt = n + 1;
	for(register int i = 1;i <= m;++ i) {
		int k = gi() , c1 = gi(), c2 = gi();sum = sum + c1 + c2;
		add_Node(s , n + (i - 1) * 2 + 2, c1);
		add_Node(n + (i - 1) * 2 + 3 , t, c2);
		for(register int j = 1;j <= k;++ j) {
			int v = gi();
			add_Node(n + (i - 1) * 2 + 2, v + 1, inf);
			add_Node(v + 1 , n + (i - 1) * 2 + 3, inf);
		}
	}
	Din::Dinic();
  return 0;
}

回复

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

正在加载回复...