@[NineQueen](/user/234344) ~~300的数组可能会爆,305的………………………………WA了~~
脱离TLE也刑,至少能思考了
by Li_mz__ @ 2022-11-16 18:17:45
没事了,已解决,就是单纯的edge数组开小了,谢谢各位
~~这个事件告诉我们,没有什么离奇事件,单纯就是自己能力不行(;′⌒`)~~
by NineQueen @ 2022-11-16 19:58:31
@[Li_mz__](/user/765987) 已解决,谢谢大佬,问题就在于最多有202个点不假,可是边最多有10000*2多条,数组开小了
by NineQueen @ 2022-11-16 20:00:05
最后附上没有内存浪费的ac代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
struct Edge{
int to,next,val;
}edge[20010];
int head[110],dis[110],ans,tot=1,up[110];
bool vis[110],school[52];
inline void addEdge(int a,int b){
//a-> b
edge[++tot].next = head[a];
edge[tot].to = b;
edge[tot].val = 1;
head[a] = tot;
edge[++tot].next = head[b];
edge[tot].to = a;
edge[tot].val = 0;
head[b] = tot;
return ;
}
int be,en;
bool dfs(){
for(int i = 0;i<=en;i++){
vis[i] = false;
}
queue<int> q;
q.push(be);
vis[be] = true;
dis[be] = INT_MAX;
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = head[x];i;i=edge[i].next){
if(!edge[i].val) continue;
int v = edge[i].to;
if(vis[v]) continue;
q.push(v);
up[v] = i;
dis[v] = min(dis[x],edge[i].val);
vis[v] = true;
if(v==en){
return true;
}
}
}
return false;
}
void update(){
int x = en;
while(x!=be){
int v = up[x];
//cout << edge[v].to <<' ';
edge[v].val -= dis[en];
edge[v^1].val += dis[en];
x = edge[v^1].to;
}
ans += dis[en];
}
void init(){
memset(edge,0,sizeof(edge));
tot = 1;
memset(head,0,sizeof(head));
ans = 0;
memset(school,false,sizeof(school));
return ;
}
int main(){
int T;
cin >> T;
while(T--){
addEdge(1,2);
init();
cin >> n;
be = 0;
en = 2*n+1;
int totstu = 0;
for(int i =1;i<=n;i++){
bool isSchool;
cin >> isSchool;
school[i] = isSchool;
if(isSchool){
addEdge(n+i,en);
}
}
for(int i = 1;i<=n;i++){
bool isHome;
cin >> isHome;
if(!school[i]){
totstu++;
addEdge(be,i);
continue;
}
if(!isHome){
totstu++;
addEdge(be,i);
}
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
bool isFriend;
cin >> isFriend;
if(i==j){
addEdge(i,n+i);
continue;
}
if(isFriend){
addEdge(i,n+j);
}
}
}
/*
for(int i = 2;i<=tot;i+=2){
cout << edge[i].from <<' '<<edge[i].to<<endl;
}
*/
while(dfs()){
update();
}
if(ans==totstu){
cout << "^_^" << endl;
}else{
cout <<"T_T"<<endl;
}
}
system("pause");
return 0;
}
```
by NineQueen @ 2022-11-16 20:00:51
@[NineQueen](/user/234344) 刑,关了
by Li_mz__ @ 2022-11-16 20:01:20