未1A原因:在拆点之后添加边的过程中,要注意,出去的是i`,进来的是i,!!所以,写addegde函数时候
还是每次添加一单项边就好,之后手动调用,可以注意出入之边即可。简单题。
#include<iostream>//15ms #include<cstdio> #include<queue> using namespace std; int n,m,start,last; int nume; int e[80000][3];int head[300];const int inf=0x3f3f3f3f; void addedge(int from,int to,int w) //添加边的函数,derect为1时要添加双向边 { e[nume][0]=to; e[nume][1]=head[from];head[from]=nume; e[nume++][2]=w; e[nume][0]=from; e[nume][1]=head[to];head[to]=nume; e[nume++][2]=0; } int level[300];int vis[300]; bool bfs() //dinic { for(int i=0;i<=2*n+1;i++) vis[i]=level[i]=0; queue<int>q;q.push(start); vis[start]=1; while(!q.empty()) { int cur=q.front();q.pop(); for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(!vis[v]&&e[i][2]>0) { level[v]=level[cur]+1; if(v==last+n)return 1; vis[v]=1; q.push(v); } } } return vis[last+n]; } int dfs(int u,int minf) { if(u==last+n||minf==0)return minf; int sumf=0,f; for(int i=head[u];i!=-1&&minf;i=e[i][1]) { int v=e[i][0]; if(level[v]==level[u]+1&&e[i][2]>0) { f=dfs(v,minf<e[i][2]?minf:e[i][2]); e[i][2]-=f;e[i^1][2]+=f; minf-=f;sumf+=f; } } return sumf; } int dinic() { int sum=0; while(bfs()) { sum+=dfs(start,inf); } return sum; } int main() { int N;scanf("%d",&N); while(N--) { scanf("%d%d%d%d",&n,&m,&start,&last); nume=0; for(int i=0;i<=2*n+1;i++) head[i]=-1; int temp,from,to; for(int i=1;i<=n;i++) { scanf("%d",&temp); if(i==start||i==last) { addedge(i,n+i,inf); addedge(n+i,i,inf); } else { addedge(i,n+i,temp); addedge(i+n,i,temp); } } for(int i=0;i<m;i++) { scanf("%d%d",&from,&to); addedge(from+n,to,inf); //这里注意一下出入边,按上面所说的。 addedge(to+n,from,inf); } int ans=dinic(); printf("%d ",ans); } }