F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 1391 >> 此题为何一直RE
Bill_Yang @ 2017-04-16 21:55:58
[ Quote ] [ Edit ] [ Delete ] 1#
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=5005;
struct Edge {
int from,to,cap,flow;
};
struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
int dist[maxn],Current[maxn];
bool vst[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int from,int to,int cap) {
edges.push_back((Edge) {
from,to,cap,0
});
edges.push_back((Edge) {
to,from,0,0
});
m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool Bfs() {
memset(dist,0,sizeof(dist));
memset(vst,0,sizeof(vst));
queue<int>Q;
Q.push(s);
dist[s]=0;
vst[s]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int i=0; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[t];
}
int Dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=Current[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]+1!=dist[Next])continue;
int Nextflow=Dfs(Next,min(a,e.cap-e.flow));
if(Nextflow>0) {
e.flow+=Nextflow;
edges[G[Now][i]^1].flow-=Nextflow;
flow+=Nextflow;
a-=Nextflow;
if(a==0)break;
}
}
return flow;
}
int MaxFlow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(Bfs()) {
memset(Current,0,sizeof(Current));
flow+=Dfs(s,0x7fffffff/2);
}
return flow;
}
} dinic;
int n,m,sum=0;
int main() {
n=Get_Int();
m=Get_Int();
int S=n+m+2,T=n+m+3;
dinic.init(n+m+5);
for(int i=1; i<=n; i++) {
int x=Get_Int();
dinic.AddEdge(S,i,x);
sum+=x;
int l=Get_Int();
for(int j=1; j<=l; j++) {
int x=Get_Int();
dinic.AddEdge(i,n+x,Get_Int());
}
}
for(int i=1; i<=m; i++)dinic.AddEdge(n+i,T,Get_Int());
printf("%d\n",sum-dinic.MaxFlow(S,T));
return 0;
}
ws_zzyer @ 2018-07-08 16:50:59
[ Quote ] [ Edit ] [ Delete ] 2#
我也是
ws_zzyer @ 2018-07-08 16:57:20
[ Quote ] [ Edit ] [ Delete ] 3#
额,可能是MLE了
[Top] [Previous Page] [Next Page]

HOME Back