基本的最小割问题做得也差不多了....
这题整死我了....
在Amber的论文里有这个解法，大家去看看吧。
其他的不说了。
这题把数据类型全都改成long long才过，瞪大眼睛找了一晚上，没找出trick.... 悲催....
如果你也WA了，不妨试试这种方法... PS：我连bool都改long long了= =|||
#include<iostream> #include<cstdio> #define INF 2100000000000560ll #define MN 5555 #define MM 555555 #define CC(a) memset( a,0,sizeof(a) ) #define FF(i,N) for( int i=0;i<N;i++ ) template<class T>inline void checkmin( T&a,T b ){ if( a>b||a==-1 ) a=b; } using namespace std;typedef long long ll; ll n,m,s,t,alloc,tot; struct edge{ll pos,next,c; }E[MM]; ll cur[MN],gap[MN],dis[MN],pre[MN],head[MN];void addEdge( ll u,ll v,ll c,ll cc=0 ) {E[alloc].pos=v;E[alloc].c=c;E[alloc].next=head[u];head[u]=alloc++;E[alloc].pos=u;E[alloc].c=cc;E[alloc].next=head[v];head[v]=alloc++; }void setG() {ll u,v,cap;CC(E);memset( head,-1,sizeof(head) );s=0,t=n+1;alloc=0;tot=0;for( int i=1;i<=n;i++ ){scanf( "%lld",&cap );if( cap>0 ){addEdge( s,i,cap );tot+=cap;}if( cap<0 )addEdge( i,t,-cap );}FF(i,m){scanf( "%d%d",&u,&v );addEdge( u,v,INF );} }ll sap() {CC(dis),CC(gap);FF( i,t+1 ) cur[i]=head[i];int u=pre[s]=s;ll maxflow=0,aug=-1;gap[0]=t+1;while( dis[s]<=t ){ loop:for( ll &i=cur[u];i!=-1;i=E[i].next ){ll v=E[i].pos;if( E[i].c&&dis[u]==dis[v]+1 ){pre[v]=u;checkmin( aug,E[i].c );u=v;if( v==t ){maxflow+=aug;//printf( "%d\n",maxflow );for( u=pre[u];v!=s;v=u,u=pre[u] )E[cur[u]].c-=aug,E[cur[u]^1].c+=aug;aug=-1;}goto loop;}}ll mind=t;for( ll i=head[u];i!=-1;i=E[i].next ){ll v=E[i].pos;if( E[i].c&&mind>dis[v] )cur[u]=i,mind=dis[v];}if( --gap[dis[u]]==0 ) break;gap[dis[u]=mind+1]++;u=pre[u];}return maxflow; }ll sum,vis[MN]; void dfs( ll cur ) {if( cur==t ) return ;sum++;vis[cur]=true;for( ll i=head[cur];i!=-1;i=E[i].next )if( vis[E[i].pos]==false&&E[i].c )dfs(E[i].pos); }int main() {while( scanf("%d%d",&n,&m)!=EOF ){setG();ll ans=tot-sap();sum=0;CC(vis);dfs(s);printf( "%lld %lld\n",sum-1,ans );}return 0; }