POJ 1815 Friendship(最小の割点dinicを求めます)

転送ゲート:http://poj.org/problem?id=1815 問題の意味はs点からt点までを求めて、少なくともいくつかの点を除いて彼らがつながっていないようにします.NO ANSWERを出力しないと!       最小割はいくつかの辺を切る解しか求められないので、私たちが要求しているのはいくつかの点を切ることです.では、各点を入点と出点に分解することを考えることができます.インポイント->アウトポイントのウェイト値は1です.では、この辺を切るのはこの点を切ることに相当し、この問題を最小割に変換することができます.では、元のエッジは、カットしたくないので、元のエッジの重み値をINFに設定します.たとえば,元のエッジがu->vであればout(u)->in(v)となる.このように1回最大流を走って、走った答えは最小カットの点数です.       この問題はまた私たちが1つの点集を求めなければならなくて、切った点で、辞書の順序によって並べます.割点は複数の組み合わせがある可能性があるので、最も簡単な考え方は列挙です.この点を切った後、走り出した答えを1つ少なく切ることができれば、この点は要求された点の一つであり、それを切って、すべての答えを挙げるまで列挙を続けます.       もっと良い方法は枚挙にいとまがないべきで、教育を求めます...コード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int INF=1e9+7;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define in(x) (x)
#define out(x) (x+n)
int n,st,ed;
int start[210][210],pic[555][555],d[555];
bool del[555];
vector<int> pr;
void build(){
    for(int i=1;i<=n;i++){
        if(!del[i])
            pic[in(i)][out(i)]=1;//  ，         ，   del    
        //   1，          ，           ，           
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)if(start[i][j]){
            pic[out(i)][in(j)]=INF;
            //        INF，         
        }
    }
}
bool BFS(){
    queue<int> Q;
    memset(d,-1,sizeof d);
    Q.push(st);d[st]=0;
    while(!Q.empty()){
        int s=Q.front();Q.pop();
        for(int i=1;i<=n+n;i++){
            if(pic[s][i]>0&&d[i]<0){
                d[i]=d[s]+1;if(i==ed)return true;
                Q.push(i);
            }
        }
    }
    return false;
}
int DFS(int s,int t,int flow){
    if(s==t||flow==0)return flow;
    int ans=0;
    for(int i=1;i<=n+n;i++){
        if(d[i]==d[s]+1&&pic[s][i]>0){
            int ff=DFS(i,t,min(pic[s][i],flow));
            if(ff>0){
                pic[s][i]-=ff;
                pic[i][s]+=ff;
                ans+=ff;
                flow-=ff;
                if(!flow)break;
            }
        }
    }
    if(!ans)d[s]=-1;
    return ans;
}
int dinic(){
    int ans=0;
    while(BFS()){
        ans+=DFS(st,ed,INF);
    }
    return ans;
}
int main()
{
//    freopen("D://input.txt","r",stdin);
    scanf("%d%d%d",&n,&st,&ed);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&start[i][j]);
        }
    }
    if(start[st][ed]){printf("NO ANSWER!
");return 0;}
    //            
    st=out(st);ed=in(ed);
    build();
    int ans=dinic();
    printf("%d
",ans);
    if(!ans)return 0;
    for(int i=1;i<=n;i++){
    //            ，         ，           ，       
        if(i==st-n||i==ed)continue;
        del[i]=true;
        build();
        int t=dinic();
        if(tif(ans==0)break;
        }
        else del[i]=false;;
    }
    for(int i=0;iint)pr.size();i++){
        if(i)printf(" ");
        printf("%d",pr[i]);
    }
    printf("
");
    return 0;
}