还是太菜了。。感觉是最小割然而不知道怎么建图。。以下是题解

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 const int maxn=1e3+5,INF=1e9; 9 struct Edge{ 10 int from,to,cap,flow; 11 Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} 12 }; 13 struct ISAP{ 14 int n,s,t; 15 vector
           
             edges; 16 vector
            
              G[maxn]; 17 bool vis[maxn]; 18 int d[maxn]; 19 int cur[maxn]; 20 int p[maxn]; 21 int num[maxn]; 22 23 void init(int n){ 24 this->n=n; 25 edges.clear(); 26 for(int i=0;i
             

Q; 39 Q.push(t); 40 d[t]=0; 41 vis[t]=1; 42 while(!Q.empty()){ 43 int x=Q.front();Q.pop(); 44 for(int i=0;i

s=s;this->t=t; 74 int flow=0; 75 BFS(); 76 memset(num,0,sizeof(num)); 77 for(int i=0;i

e.flow&&d[x]==d[e.to]+1){ 89 ok=1; 90 p[e.to]=G[x][i]; 91 cur[x]=i; 92 x=e.to; 93 break; 94 } 95 } 96 if(!ok){ 97 int m=n-1; 98 for(int i=0;i

e.flow)m=min(m,d[e.to]);101 }102 if(--num[d[x]]==0)break;103 num[d[x]=m+1]++;104 cur[x]=0;105 if(x!=s)x=edges[p[x]].from;106 }107 }108 return flow;109 }110 }isap;111 112 inline int ABS(int x){ return x>=0?x:-x;}113 int n,m;114 int g[maxn][maxn];115 int main(){116 memset(g,0,sizeof(g));117 scanf("%d%d",&n,&m);118 isap.init(n+2);119 for(int i=0;i