POJ 2987 最大权闭合子图 - c++编程基础

].cap-edge[S[i]].flow,id=i; for(ll i=0;i edge[i].flow)dfs1(v); } } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); ll n,m; while(~scanf("%lld%lld",&n,&m)){ memset(head,-1,sizeof(head));tol=0; ll sum=0; for(ll i=1;i<=n;i++){ ll w; scanf("%lld",&w); if(w>0){ sum+=w; addedge(0,i,w); } else{ addedge(i,n+1,-w); } } while(m--){ ll u,v; scanf("%lld%lld",&u,&v); addedge(u,v,INF); } ll pp=sap(0,n+1,n+10); ll ans=0; memset(col,0,sizeof(col)); dfs1(0); //for(ll i=1;i<=n;i++)cout<

dinic一直跑不出样例，原来是模板里一个分号错误的打成逗号，又检查出模板的一个bug。

dinic代码：

/* ***********************************************
Author :rabbit
Created Time :2014/3/8 10:05:50
File Name :1718.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
                    
                     
#include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                         
                           #include 
                          
                            #include 
                           
                             #include 
                            
                              #include 
                             
                               #include 
                              
                                #include 
                               
                                 #include 
                                
                                  #include 
                                  using namespace std; #define INF 100000000000000LL #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; const ll maxn=6110; const ll maxm=400010; struct Edge{ ll to,next,cap; Edge(){}; Edge(ll _next,ll _to,ll _cap){ next=_next;to=_to;cap=_cap; } }edge[maxm]; ll head[maxn],tol,dep[maxn],cur[maxn],n; void addedge(ll u,ll v,ll flow){ edge[tol]=Edge(head[u],v,flow);head[u]=tol++; edge[tol]=Edge(head[v],u,0);head[v]=tol++; } ll Q[maxn]; bool bfs(ll start,ll end){ memset(dep,-1,sizeof(dep)); ll front=0,rear=0; dep[start]=0;Q[rear++]=start; while(front!=rear){ ll u=Q[front++]; for(ll i=head[u];i!=-1;i=edge[i].next){ ll v=edge[i].to;if(dep[v]==-1&&edge[i].cap>0){ Q[rear++]=v,dep[v]=dep[u]+1; if(v==end)return 1; } } } return 0; } ll dinic(ll s,ll t){ ll i,res=0,top; ll S[maxn]; while(bfs(s,t)){ memcpy(cur,head,sizeof(head)); ll u=s;top=0; while(1){ if(u==t){ ll min=INF,id; for(ll i=0;i
                                  
                                   0)dfs1(v); } } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); ll n,m; while(~scanf("%lld%lld",&n,&m)){ memset(head,-1,sizeof(head));tol=0; ll sum=0; for(ll i=1;i<=n;i++){ ll w; scanf("%lld",&w); if(w>0){ sum+=w; addedge(0,i,w); } else{ addedge(i,n+1,-w); } } while(m--){ ll u,v; scanf("%lld%lld",&u,&v); addedge(u,v,INF); } ll pp=dinic(0,n+1); ll ans=0; memset(col,0,sizeof(col)); dfs1(0); //for(ll i=1;i<=n;i++)cout<

POJ 2987 最大权闭合子图(二)