考试的时候有思路了，但是没写完。这题起码要40min写，思路太诡异了。
刚刚写了一段，只过了一个case，得了18分，还行。明日再战。
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 50000 #define MAX 0x06FFFFFF using namespace std; vector<int> v[1000]; int cnt=1; map<int,int> ID2index; void buildConnect(int a,int b); bool judge(int mul,int pos); int mode=0; typedef struct CP{ int a,b; CP(int A,int B){a=A;b=B;} }CP; bool cmp(CP a,CP b); int main() { freopen("d:/input/A1139.txt","r",stdin); int n,m,k; scanf("%d%d",&n,&m); while(m-->0){ int a,b; scanf("%d %d",&a,&b); buildConnect(a,b); buildConnect(b,a); } scanf("%d",&k); while(k-->0){ int a,b,i,j,k; scanf("%d %d",&a,&b); mode= a*b>0 ? 1 : 0 ; vector<CP> ot; int i1=ID2index[a],i2,i3; int O1,O2; FF(i,v[i1].size()) if(judge(v[i1][i]*a,0)){//find tongXing O1=v[i1][i]; i2=ID2index[O1];//is tongXing FF(j,v[i2].size()) if(judge(v[i2][j]*a,1)){//find yiXing O2=v[i2][j]; i3=ID2index[O2];//is yiXing FF(k,v[i3].size()) if(v[i3][k]==b){//find object CP tmp(abs(O1),abs(O2)); ot.push_back(tmp); break; } } } int s=ot.size(); sort(ot.begin(),ot.end(),cmp); O("%d ",s); FF(i,s) O("%d %d ",ot[i].a,ot[i].b); } return 0; } void buildConnect(int a,int b){ int index=ID2index[a]; if(index>0){//find v[index].push_back(b); }else{ ID2index[a]=cnt;//cnt is a new index v[cnt++].push_back(b); } } bool cmp(CP a,CP b){ if(a.a<b.a) return true; else if(a.a==b.a && a.b<b.b) return true; return false; } bool judge(int mul,int pos){ if(mode==0){ if(pos==0 && mul>0)return true; if(pos==1 && mul<0)return true; } if(mode==1){ if(pos==0 && mul>0)return true; if(pos==1 && mul>0)return true; } return false; }
2017年3月14日，24分：
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 10000 #define MAX 0x06FFFFFF #define V vector<int> using namespace std; typedef struct Node{ int a,b; Node(int a=0,int b=0):a(a),b(b){ } bool operator < (const Node& obj) const { if(a<obj.a || (a==obj.a && b<obj.b)) return 1; return 0; } }; vector<int> adj[LEN]; int isg[LEN]; int vis[LEN]; vector<int> path; set<Node> ans; int N,M,K; //dfs(s,e,0,mode); void dfs(int s,int e,int cnt,int mode){ if(cnt>3) return; if(s==e && cnt==3){ ans.insert(Node(path[0],path[1])); return; } int i; FF(i,adj[s].size()){ int o=adj[s][i]; if(vis[o]==0){ bool isOK=0; if(mode<0){ if(cnt%2==0 && isg[s]*isg[o]>0) isOK=1; if(cnt%2==1 && isg[s]*isg[o]<0) isOK=1; }else{ if(isg[s]*isg[o]>0) isOK=1; } if(isOK){ vis[o]=1; path.push_back(o); dfs(o,e,cnt+1,mode); path.pop_back(); vis[o]=0; } } } } int proc(int a){ if(a<0){ a=-a; isg[a]=-1; }else{ isg[a]=1; } return a; } int main(){ // freopen("1139.txt","r",stdin); int s,e,i,j,a,b; I("%d%d",&N,&M); while(M--){ I("%d%d",&a,&b); a=proc(a); b=proc(b); adj[a].push_back(b); adj[b].push_back(a); } I("%d",&K); while(K--){ I("%d%d",&s,&e); int mode=s*e; s=abs(s); e=abs(e); ans.clear(); path.clear(); vis[s]=1; dfs(s,e,0,mode); vis[s]=0; set<Node>::iterator it=ans.begin(); O("%d ",ans.size()); while(it!=ans.end()){ O("%04d %04d ",it->a,it->b); it++; } } return 0; }