题解 P3005 【[USACO10DEC]The Trough Game S】
Mobius127
·
·
题解
传送门
link
什么叫暴力出奇迹啊(狗头
看到N \leqslant20 直接暴力Food Filled，填完之后O(nm)检查是否可行即可。
主程序：
void dfs(int k){
if(k>n){
bool flag=true;
int s=0;
for(int i=1; i<=m; i++){
s=0;
for(int j=1; j<=n; j++){
if(str[i][j]=='1'){
s+=u[j];
}
}
if(s!=sum[i]) flag=false;
}
if(flag){
ans++;
for(int i=1; i<=n; i++) Ans[i]=u[i];
}
return ;
}
dfs(k+1);u[k]=1;dfs(k+1);u[k]=0;
}
交完仔细分析，欸这复杂度不对啊。
~~bfs~~思考了一会儿后，找到了这个东西：
```
exit(0);
```
能直接结束整个程序的运行。
### 好东西啊！
可还是超时了。~~别打~~
思考剪枝，只要有1个不符合匹配，就可以直接$break$。
于是复杂度就大大降低了。
## AC Code:
```cpp
#include <stdio.h>
#include <algorithm>
#define N 1005
using namespace std;
int n, m, u[N], ans, Ans[N];
char str[N][N];int sum[N];
void dfs(int k){
if(k>n){
bool flag=true;
int s=0;
for(int i=1; i<=m; i++){
s=0;
for(int j=1; j<=n; j++){
if(str[i][j]=='1'){
s+=u[j];
}
}
if(s!=sum[i]){
flag=false;
break;
}
}
if(flag){
ans++;
if(ans>1){
printf("NOT UNIQUE");
exit(0);
}
for(int i=1; i<=n; i++) Ans[i]=u[i];
}
return ;
}
dfs(k+1);u[k]=1;dfs(k+1);u[k]=0;
}
int main(){
scanf("%d%d", &n, &m);
for(int i=1; i<=m; i++) scanf("%s%d", str[i]+1, &sum[i]);
dfs(1);
if(ans==0) printf("IMPOSSIBLE");
else for(int i=1; i<=n; i++) printf("%d", Ans[i]);
return o;
}
```