题目本身还是比较水的吧……容易发现是最大流套上dinic跑一遍就好了，并不会超时。
比较不偷税的一点是关于某动物的所有目击报告都符合才能连边……qwqqwqqwq
#include<cstdio> #include<algorithm> #include<cctype> #include<cstring> #include<cstdlib> #include<queue> #define maxn 1000 using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } int u[5]={0,0,1,0,-1}; int w[5]={0,1,0,-1,0}; struct Edge{ int next,to,val; }edge[maxn*2]; int head[maxn],num; inline void addedge(int from,int to,int val){ edge[++num]=(Edge){head[from],to,val}; head[from]=num; } inline void add(int from,int to,int val){ addedge(from,to,val); addedge(to,from,0); } inline int count(int i){ return i&1?i+1:i-1; } int pre[maxn]; int Start,End; bool vis[maxn]; int dfn[maxn]; int list[maxn]; bool bfs(){ memset(vis,0,sizeof(vis)); dfn[Start]=1; vis[Start]=1; queue<int>q; q.push(Start); while(!q.empty()){ int from=q.front(); q.pop(); for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(vis[to]||edge[i].val<=0) continue; vis[to]=1; dfn[to]=dfn[from]+1; q.push(to); } } return vis[End]; } int dfs(int x,int val){ if(val==0||x==End) return val; vis[x]=1; int flow=0; for(int &i=list[x];i;i=edge[i].next){ int to=edge[i].to; if(vis[to]||dfn[to]!=dfn[x]+1||edge[i].val<=0) continue; int now=dfs(to,min(val,edge[i].val)); if(x!=End) pre[to]=x; edge[i].val-=now; edge[count(i)].val+=now; val-=now; flow+=now; if(val<=0) break; } if(val!=flow) dfn[x]=-1; return flow; } inline int maxflow(){ int ans=0; while(bfs()){ memset(vis,0,sizeof(vis)); for(int i=Start;i<=End;++i) list[i]=head[i]; int now=dfs(Start,0x7fffffff); if(now==0) break; ans+=now; } return ans; } int s[maxn][maxn]; char c[maxn]; bool ext[maxn][maxn]; int dis[105][105][105]; int v[maxn]; bool exa[maxn]; int f[maxn][maxn]; int sum[maxn]; struct Node{ int x,y; }que[maxn]; int main(){ memset(dis,127/3,sizeof(dis)); int inf=dis[0][0][0]; int n=read(); for(int i=1;i<=n;++i){ scanf("%s",c+1); for(int j=1;j<=n;++j) if(c[j]=='*') s[i][j]=1; else s[i][j]=0; } int p=read(); End=p*2+1; for(int i=1;i<=p;++i) que[i]=(Node){read(),read()}; for(int i=1;i<=p;++i){ add(Start,i,1); add(i+p,End,1); queue<Node>q; q.push(que[i]); dis[i][que[i].x][que[i].y]=0; while(!q.empty()){ Node from=q.front(); q.pop(); //printf("%d %d %d<<<<<<<< ",i,from.x,from.y); for(int j=1;j<5;++j){ int nx=from.x+u[j]; int ny=from.y+w[j]; //printf("%d %d %d %d><> ",nx,ny,s[nx][ny],dis[i][from.x][from.y]); if(nx<1||nx>n||ny<1||ny>n||s[nx][ny]||dis[i][nx][ny]!=inf) continue; dis[i][nx][ny]=dis[i][from.x][from.y]+1; q.push((Node){nx,ny}); } } } for(int i=1;i<=p;++i) v[i]=read(); int r=read(); for(int i=1;i<=r;++i){ int t=read(),x=read(),y=read(),d=read(); sum[d]++; for(int j=1;j<=p;++j){ //printf("%d %d>>> ",j,dis[j][x][y]); int ret=v[d]*t; if(ret>=dis[j][x][y]) f[j][d]++; } } for(int i=1;i<=p;++i) for(int j=1;j<=p;++j) if(sum[i]==f[j][i]) add(j,i+p,1); maxflow(); for(int i=1+p;i<End;++i){ for(int j=head[i];j;j=edge[j].next){ int to=edge[j].to; if(to==End||edge[j].val==0) continue; printf("%d %d %d ",i-p,que[to].x,que[to].y); break; } } return 0; }