Science!

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 415 Accepted Submission(s): 116
Special Judge

Problem Description Welcome, ladies and gentlemen, to Aperture Science. Astronauts, War Heroes, Olympians — you’re here because we want the best, and you are it. That said, it’s time to make some science.
Now, I want each of you to stand on one of these buttons. Well done, we’re making great progress here. Now let’s do it again. Oh, come on - don’t stand on the same button! Move, people! No, no, that button’s only for the Astronauts, you know who you are. What?! You say you can’t do everything I ask? Ok let’s start over. You there, the Programmer, figure out how many times we can do this. And make it quick, we have a lot more science to get through…
Input There will be several test cases in the input. The first line of each case will contain n (2≤n≤80) giving the number of people (and the number of buttons) in the experiment. The next n lines will contain n characters each. If the j^th character of the i^th line is Y it indicates that the i^th person can stand on the j^th button (it is N otherwise). The last line of input will be a 0.
Output For each test case, output k, the maximum number of times everyone can be standing on buttons such that nobody stands on the same button more than once (This might be 0). After that, output k lines. Each line should contain n integers separated by single spaces, where the i^th integer describes which person is standing on the i^th button. All of the lines should be valid and none of them should put the same person on the same button as a previous line of the same test case. Output no extra spaces, and do not separate answers with blank lines. Note that correct outputs might not be unique.
Sample Input

3
YYY
NYY
YNY
2
YN
YN
0

Sample Output

2
3 1 2
1 2 3
0

Source The University of Chicago Invitational Programming Contest 2012
Recommend liuyiding | We have carefully selected several similar problems for you: 5390 5389 5388 5387 5386

 

二分答案網絡流，求出k.

刪除多余邊，

接下來k次，

每次在原圖上找最大二分圖匹配，刪除邊，

得到一個可行解

 

 

 

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXn (80+10)
#define MAXN (500+19)
#define MAXM (69999+100)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
class Max_flow  //dinic+當前弧優化   
{    
public:    
    int n,s,t;    
    int q[MAXN];    
    int edge[MAXM],next[MAXM],pre[MAXN],weight[MAXM],size;    
    void addedge(int u,int v,int w)      
    {      
        edge[++size]=v;      
        weight[size]=w;      
        next[size]=pre[u];      
        pre[u]=size;      
    }      
    void addedge2(int u,int v,int w){addedge(u,v,w),addedge(v,u,0);}     
    bool b[MAXN];    
    int d[MAXN];    
    bool SPFA(int s,int t)      
    {      
        For(i,n) d[i]=INF;    
        MEM(b)    
        d[q[1]=s]=0;b[s]=1;      
        int head=1,tail=1;      
        while (head<=tail)      
        {      
            int now=q[head++];      
            Forp(now)      
            {      
                int &v=edge[p];      
                if (weight[p]&&!b[v])      
                {      
                    d[v]=d[now]+1;      
                    b[v]=1,q[++tail]=v;      
                }      
            }          
        }      
        return b[t];      
    }     
    int iter[MAXN];  
    int dfs(int x,int f)  
    {  
        if (x==t) return f;  
        Forpiter(x)  
        {  
            int v=edge[p];  
            if (weight[p]&&d[x]>1;
			if (check(m)) ans=m,l=m+1;
			else r=m-1;
		}
		
		check(ans);
			
		printf(%d
,ans);
		Fork(i,2,n+1)
		{
			for(int p=S.pre[i];p;p=S.next[p])
				if (!S.weight[p^1]&&S.edge[p]>n+1) s[i-1][S.edge[p]-n-1]='N'; 
			
		}
	
		while (ans--)
		{
			S.mem(2*n+2,1,2*n+2);
			For(i,n) S.addedge2(1,i+1,1),S.addedge2(n+1+i,2*n+2,1);
			For(i,n) For(j,n) if (s[i][j]=='Y') S.addedge2(1+i,n+1+j,1);
			S.max_flow(1,2*n+2);
			
		
			
			Fork(i,2,n+1)
			{
				for(int p=S.pre[i];p;p=S.next[p])
					if (!S.weight[p]&&S.edge[p]>n+1)
					{
						Ans[S.edge[p]-n-1]=i-1,s[i-1][S.edge[p]-n-1]='N'; 
						break;
					}
			}
			
			For(i,n-1) printf(%d ,Ans[i]);printf(%d
,Ans[n]);
	
			
		}	
		
	}
	
	return 0;
}