首页 > 代码库 > bzoj1059题解

bzoj1059题解

2024-09-10 17:00:30   215人阅读

【解题思路】

　　因为只要验证可行性，所以考虑行和考虑列是等价的，故我们只考虑行的交换操作。

　　这样，拆一波点，把每一行拆成两个点，左边为原交换行，右边为目标交换行，原问题等价于能否对这个二分图进行完全匹配，题中给定邻接矩阵即为二分图的邻接矩阵。

　　于是直接匈牙利一波，复杂度O(n3)。

【参考代码】

技术分享
 1 #include <cctype> 2 #include <cstdio> 3 #define REP(I,low,high) for(register int I=(low);I<=(high);I++) 4 #define PER(I,high,low) for(register int I=(high);I>=(low);I--) 5 inline int getint() 6 { 7     char ch=getchar(); 8     for(;!isdigit(ch)&&ch!=‘+‘&&ch!=‘-‘;ch=getchar()); 9     bool impositive=ch==‘-‘;10     if(impositive)11         ch=getchar();12     int result=0;13     for(;isdigit(ch);ch=getchar())14         result=(result<<3)+(result<<1)+ch-‘0‘;15     return impositive?-result:result;16 }17 template<typename integer> inline int write(integer n)18 {19     integer now=n;20     bool impositive=now<0;21     if(impositive)22     {23         putchar(‘-‘);24         now=-now;25     }26     char sav[40];27     sav[0]=now%10+‘0‘;28     int result=1;29     for(;now/=10;sav[result++]=now%10+‘0‘);30     PER(i,result-1,0)31         putchar(sav[i]);32     return result+impositive;33 }34 //Header Template35 #include <cstring>36 bool used[210],map[210][210];37 int n,result[210];38 bool find(int S)39 {40     REP(T,1,n)41         if(map[S][T]&&!used[T])42         {43             used[T]=true;44             if(!result[T]||find(result[T]))45             {46                 result[T]=S;47                 return true;48             }49         }50     return false;51 }52 int main()53 {54     for(int T=getint();T--;)55     {56         n=getint();57         REP(i,1,n)58             REP(j,1,n)59                 map[i][j]=getint();60         memset(result,0,sizeof(result));61         int ans=0;62         REP(i,1,n)63         {64             memset(used,0,sizeof(used));65             ans+=find(i);66         }67         puts(ans==n?"Yes":"No");68     }69     return 0;70 }
View Code

 

bzoj1059题解


联系
我们