题目大意：有n个员工，每个员工通讯录里有自己的号码和其他一些员工的号码。现在有若干员工参加一个聚会，他们会给自己通讯录里所有的人发一条短信，包括自己。现在有个人预测了每个员工会收到多少条短信，而你要寻找一种员工参与聚会的情况，也就是决定哪些员工参与聚会，能够使对所有员工的预测都错误。n<=100

也就是有一个n*n的01矩阵，其中对角线一定是1，要选定一些行，使得这些选定的行每一列的和不等于给定的一个预测值。

 

这个是大一六月份做的，看了下代码简单到可怕，当然也就理所当然的WA了。

想了一会发现其实没有很好的思路，看了一下tourist大佬的代码，简直精美。。。。

感叹自己还是太菜了啊

 

这是一个思路很精妙的贪心，主要切入点在于每个人的通讯录里一定有自己，所以只要我们安排，每个人都能收到短信，即可以防止任何人的预测值为0的情况。

那么我们首先找是否有人预测值是0，也就是是否有列的预测值是0。如果有，那么我们就把该行选来聚会，此时这个人自己肯定会收到自己给自己的短信，即收到的短信数大于0了。此时最重要的一点是，我选择了这个人他自己来解决他自己的问题后，无论后续再选多少人，有多少人会给他发短信，他的预测值都不可能是正确的了。

既然选了他去聚会，他就要给通讯录里所有人都发短信，所以可以将他通讯录里所有人的预测值减1，得到剩余预测值，即在除这行以外，我要选择的剩余行，其每列的和不能等于剩余预测值。

 

这样就可以不断解决剩余预测值为0的人，方法就是把他选去聚会。一旦一个人被选取聚会，也就意味着他以后再也不会预测值出问题了。因此n轮内一定能使所有剩余预测值都不为0。

问题就解决了。

 

所以贪心的证明点在于，一旦有人预测值为0，我可以通过立即将他选掉来解决，并且他以后预测值都不会为0了。这样n轮每轮解决一个，必定能解决所有n个人的预测值问题。

 

1 #include 
      
        2 using namespace std; 3 #define PB push_back 4 #define MP make_pair 5 typedef long long ll; 6 const int mod = 1e9 + 7; 7 const int INF = 0x3f3f3f3f; 8 const double eps = 1e-8; 9 const int maxn = 105;10 11 char s[maxn][maxn];12 int cnt[maxn];13 int ans[maxn],c = 0;14 int n;15 16 int main(){17     scanf("%d",&n);18     for(int i = 1 ; i <= n ; ++ i)scanf("%s",s[i]+1);19     for(int i = 1 ; i <= n ; ++ i)scanf("%d",&cnt[i]);20     for(int t = 1 ; t <= n ; ++ t){21         for(int i = 1 ; i <= n ; ++ i){22             if(cnt[i])continue;23             ans[++c] = i;24             for(int j = 1 ; j <= n ; ++ j){25                 if(s[i][j] != '0')cnt[j] -- ;26             }27         }28     }29     sort(ans + 1 , ans + c +1);30     printf("%d\n",c);31     for(int i = 1 ; i <= c ; ++ i)printf("%d ",ans[i]);32     printf("\n");33     return 0;34 }