首页 > ACM题库 > HDU-杭电 > hdu 4265-science!-分治-[解题报告]hoj
2015
05-23

hdu 4265-science!-分治-[解题报告]hoj

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 jth character of the ith line is
Y it indicates that the ith person can stand on the jth 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 ith integer describes which person is standing on the ith 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
 

Recommend
liuyiding   |   We have carefully selected several similar problems for you:  5390 5389 5388 5387 5386 
 


二分答案网络流,求出k.

删除多余边,

接下来k次,

每次在原图上找最大二分图匹配,删除边,

得到一个可行解

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
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<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;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]<d[v])  
            {  
                  int nowflow=dfs(v,min(weight[p],f));  
                  if (nowflow)  
                  {  
                    weight[p]-=nowflow;  
                    weight[p^1]+=nowflow;  
                    return nowflow;  
                  }  
            }  
        }  
        return 0;  
    }  
    int max_flow(int s,int t)  
    {  
        int flow=0;  
        while(SPFA(s,t))  
        {  
            For(i,n) iter[i]=pre[i];  
            int f;  
            while (f=dfs(s,INF))  
                flow+=f;   
        }  
        return flow;  
    }   
    void mem(int n,int s,int t)    
    {    
        (*this).n=n;  
        (*this).t=t;    
        (*this).s=s;    
          
        size=1;    
        MEM(pre)   
    }    
}S;    

char s[MAXn][MAXn];
int n;
bool check(int m)
{
	S.mem(2*n+2,1,2*n+2);
	For(i,n) S.addedge2(1,i+1,m),S.addedge2(n+1+i,2*n+2,m);
	For(i,n) For(j,n) if (s[i][j]=='Y') S.addedge2(1+i,n+1+j,1);

	if (S.max_flow(1,2*n+2)==n*m) return 1;
	return 0;
}

int Ans[MAXn];

int main()
{
//	freopen("hdu4265.in","r",stdin);
//	freopen(".out","w",stdout);
	
	while(scanf("%d",&n)==1)
	{
		if (!n) break;
		For(i,n) scanf("%s",s[i]+1);
		
		int l=0,r=n,ans=0;
		while(l<=r)
		{
			int m=(l+r)>>1;
			if (check(m)) ans=m,l=m+1;
			else r=m-1;
		}
		
		check(ans);
			
		printf("%d\n",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\n",Ans[n]);
	
			
		}	
		
	}
	
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。