求助,测试数据过不了
#include<bits/stdc++.h>
#define maxn 1210
#define maxe 3000010
using namespace std;
const int INF=1e9;
int dis[maxn],vis[maxn],head[maxn],tot;
int n,m,Cost=0,Flow=0;
struct zkw
{
struct Edge
{
int v,cap,cost,nxt;
}g[maxe];
void init(int _n)
{
tot=0;
memset(head,-1,sizeof(head));
Cost=0,Flow=0;
n=_n;
}
void add(int u,int v,int cap,int cost)
{
g[tot]={v,cap,cost,head[u]};
head[u]=tot++;
}
void jb(int u,int v,int cap,int cost)//建边!!!!
{
add(u,v,cap,cost);
add(v,u,0,-cost);
}
bool spfa(int S,int T)
{
for(int i=0;i<=n;i++)
vis[i]=0,dis[i]=INF;
deque<int>Q;
Q.push_back(T);
dis[T]=0;vis[T]=1;
while(!Q.empty())
{
int u=Q.front();Q.pop_front();
for(int i=head[u],v;~i;i=g[i].nxt)
if(g[i^1].cap&&dis[v=g[i].v]>dis[u]+g[i^1].cost)
{
dis[v]=dis[u]+g[i^1].cost;
if(!vis[v])
{
vis[v]=1;
if(!Q.empty()&&dis[v]<dis[Q.front()])
Q.push_front(v);
else Q.push_back(v);
}
} vis[u]=0;
}
return dis[S]<INF;
}
int dfs(int S,int T,int flow)
{
if(S==T)
{
vis[T]=1;
return flow;
}
int used=0,res;vis[S]=1;
for(int i=head[S],v;~i;i=g[i].nxt)
if(!vis[v=g[i].v]&&g[i].cap&&dis[S]-g[i].cost==dis[v])
{
res=dfs(v,T,min(g[i].cap,flow-used));
if(res) Cost+=res*g[i].cost,g[i].cap-=res,g[i^1].cap+=res,used+=res;
if(used==flow) break;
}
return used;
}
void solve(int S,int T)
{
while(spfa(S,T))
{
vis[T]=1;
while(vis[T]) memset(vis,0,sizeof(vis)),Flow+=dfs(S,T,INF);
}
}
};
zkw ww;
int main()
{
scanf("%d%d",&n,&m);
ww.init(n);
int res=0;
for(int i=1;i<=n;i++)
{
int x,t;
scanf("%d%d",&x,&t);
ww.jb(0,i,x,0);
res+=x;
for(int j=1;j<=t;j++)
{
int a,b;
scanf("%d%d",&a,&b);
ww.jb(i,n+a,b,0);
}
}
for(int i=1;i<=m;i++)
{
int ff;
scanf("%d",&ff);
ww.jb(i+n,m+n+1,ff,0);
}
ww.solve(0,n+m+1);
printf("%d",res-Flow);
return 0;
};
我用的是费用流的版,cost设为0,去做了一遍费用流和网络流都没问题