一道不算太难的题目

但是真的很恶心

显然，对于第一问，我们直接无脑打模板就好了

第二问也不是很难，我们将每条边再连一条容量为inf，费用为w的边

 但是流量只要小于第一问的答案加k就行了

所以我们增加一个点为第二问的汇点，将n与它连接一条容量为ans+k，费用为0的边

跑费用流就好了

但是！！！！！！！

这样作只有40分，为什么呢。

因为虽然数据范围说n<=1000但给的点编号有大于1000的点。。。。。

我们只要将点数视为5000就可以过来了

真的恶心。。。。

不过在考场上还是建议用离散化，毕竟你不知道点数编号的范围

想问一问当初省选时有多少人被这个给坑了。。

 

# include
     
      # include
      
       # include
       
        # include
        
         # include
         
          # include
          
           using namespace std;const int mn = 5005;const int inf = 0xfffffff;struct edge{int to,next,flow,cup,cost;edge(){to=flow=cup=cost=0,next=-1;}};edge e[mn*10];int head[mn],edge_max=-1;void add(int x,int y,int k,double c){ e[++edge_max].to=y; e[edge_max].next=head[x]; e[edge_max].flow=e[edge_max].cup=k; e[edge_max].cost=c; head[x]=edge_max;}int n,m,k;int ans1,ans2;int deep[mn];int cur[mn];queue
           
             q;bool bfs(int x,int y){ memset(deep,0,sizeof(deep)); q.push(x); deep[x]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=e[i].next) { if(deep[e[i].to]==0 && e[i].flow>0 ) { deep[e[i].to]=deep[u]+1; q.push(e[i].to); } } } if(deep[y]==0) return false; else return true;}int dfs(int x,int dist,int y){ if(x==y) return dist; for(int &i=cur[x];i!=-1;i=e[i].next) { if(deep[e[i].to]==deep[x]+1 && e[i].flow!=0) { int di=dfs(e[i].to,min(dist,e[i].flow),y); if(di>0) { e[i].flow-=di; e[i^1].flow+=di; return di; } } } return 0;}void dinic(int x,int y){ while(bfs(x,y)) { for(int i=1;i<=n;i++) cur[i]=head[i]; while(int k=dfs(x,inf,y)) ans1+=k; }}int dis[mn];int pe[mn],pv[mn];bool vis[mn];bool spfa(int x,int y){ memset(vis,0,sizeof(vis)); for(int i=1;i<=n+1;i++) dis[i]=inf; dis[x]=0; vis[x]=1; q.push(x); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=e[i].next) { if(dis[u]+e[i].cost
            
             0) { dis[e[i].to]=e[i].cost+dis[u]; pe[e[i].to]=i; pv[e[i].to]=u; if(!vis[e[i].to]) { q.push(e[i].to); vis[e[i].to]=1; } } } } if(dis[y]!=inf) return true; else return false;}void max_flow(int x,int y){ while(spfa(x,y)) { int mflow=inf; for(int i=y;i!=x;i=pv[i]) { mflow=min(mflow,e[pe[i]].flow); } ans2+=dis[y]*mflow; for(int i=y;i!=x;i=pv[i]) { e[pe[i]].flow-=mflow; e[pe[i]^1].flow+=mflow; } }}int a1[mn],a2[mn],a3[mn],a4[mn];void pre(){ memset(head,-1,sizeof(head)); memset(e,-1,sizeof(e)); for(int i=1;i<=m;i++) { add(a1[i],a2[i],a3[i],0); add(a2[i],a1[i],0,0); add(a1[i],a2[i],inf,a4[i]); add(a2[i],a1[i],0,-a4[i]); }}int main(){ int x,y,c,w; memset(head,-1,sizeof(head)); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&a1[i],&a2[i],&a3[i],&a4[i]); add(a1[i],a2[i],a3[i],0); add(a2[i],a1[i],0,0); } dinic(1,n); pre(); add(n,n+1,ans1+k,0); add(n+1,n,0,0); max_flow(1,n+1); printf("%d %d",ans1,ans2); return 0;}