1 条题解
-
0
C++ :
#include<cstdio> #include<cstring> int n,m,i,j,d[302],de[100005],val[302]; int ch; inline int getint() { for(ch=getchar();ch<'0'||ch>'9';ch=getchar()); int i1=ch-'0'; for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())i1=((i1<<3)+(i1<<1)+ch-'0'); return i1; } int first[702],nxt[300005],e[300005],tope,ps,pt; long long c[300005]; long long ans; inline void link(int u0,int v0,long long w0) { ++tope; e[tope]=v0; nxt[tope]=first[u0]; first[u0]=tope; c[tope]=w0; ++tope; e[tope]=u0; nxt[tope]=first[v0]; first[v0]=tope; c[tope]=0; return; } inline void buildgraph() { memset(first,0,sizeof(first)); tope=1; int i1,i2; ps=(n<<1)+1;pt=ps+1; for(i1=1;i1<=n;++i1) { link(ps,i1,987654321-val[i1]); ans+=987654321-val[i1]; link(i1+n,pt,987654321); for(i2=d[i1-1]+1;i2<=d[i1];++i2)link(i1,de[i2]+n,9876543210654321ll); } return; } int dis[702],cur[702]; int q[702],lq,rq; inline int bfs() { memset(dis,-1,sizeof(dis)); q[rq=1]=ps; dis[ps]=0; int i1; for(lq=1;lq<=rq;++lq) { cur[q[lq]]=first[q[lq]]; for(i1=first[q[lq]];i1;i1=nxt[i1]) { // printf("(%d,%d),c=%lld\n",q[lq],e[i1],c[i1]); if((c[i1]<=0)||(dis[e[i1]]>=0))continue; dis[e[i1]]=dis[q[lq]]+1; q[++rq]=e[i1]; } } return dis[pt]; } inline long long dinic(const int v1,const int v2,const long long x0) { if(v1==v2)return x0; int i1; long long i2=x0,i3; for(i1=cur[v1];i1;i1=nxt[i1]) { if((c[i1]>0)&&(dis[e[i1]]==dis[v1]+1)) { i3=dinic(e[i1],v2,(c[i1]<i2)?c[i1]:i2); if(i3<=0)continue; c[i1]-=i3; c[i1^1]+=i3; i2-=i3; if(i2<=0)break; } } cur[v1]=i1; return x0-i2; } inline long long maxflow() { long long i1=0; while(bfs()>=0) { i1+=dinic(ps,pt,987654321012345ll); } return i1; } int main() { n=getint(); memset(d,0,sizeof(d)); for(i=1;i<=n;++i) { d[i]=getint(); d[i]+=d[i-1]; for(j=d[i-1]+1;j<=d[i];++j)de[j]=getint(); } for(i=1;i<=n;++i)scanf("%d",&val[i]); ans=0; buildgraph(); ans-=maxflow(); printf("%lld",-ans); return 0; }
- 1
信息
- ID
- 166
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者