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