Category: 搜索

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1415
数据生成器：http://paste.ubuntu.com/22417252/

论文题，记忆化深搜
我在处理该去哪时，用的三方的floyd
然而hzwer告诉我，平方的bfs就好QAQ，反正没有T，我就不改啦！(づ￣ 3￣)づ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000+9;
const int INF = 1000000;
const double sta = -0.5;

int n,m,C,M,d[MAXN][MAXN],to[MAXN][MAXN],cnt[MAXN];
double ans[MAXN][MAXN];

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline void Floyd(){
	for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) if (d[i][k] < INF) 
		for (int j=1;j<=n;j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int k=1;k<=n;k++) 
		if (d[i][k] == 1 && d[k][j] == d[i][j]-1) {to[i][j] = k; break;}
	for (int i=1;i<=n;i++) to[i][i] = i;
}

double Get_Ans(int u, int v){
	if (ans[u][v] > sta) return ans[u][v];
	else {
		if (to[to[u][v]][v] != v) {
			ans[u][v] = Get_Ans(to[to[u][v]][v],v)+1;
			for (int i=1;i<=n;i++) if (d[v][i] == 1) ans[u][v] += Get_Ans(to[to[u][v]][v],i)+1;
			return ans[u][v] /= cnt[v];
		} else return ans[u][v] = 1;
	}
}

int main(){ 
	n = read(); m = read(); C = read(); M = read();
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) d[i][j] = INF, ans[i][j] = -1;
	for (int i=1;i<=n;i++) d[i][i] = 0, ans[i][i] = 0, cnt[i] = 1;
	for (int i=1,a,b;i<=m;i++) cnt[a = read()]++, cnt[b = read()]++, d[a][b] = d[b][a] = 1;
	Floyd(); printf("%.3lf\n",Get_Ans(C,M));
	return 0;
} 

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1770
离线版题目：http://paste.ubuntu.com/18956597/
数据生成器：http://paste.ubuntu.com/18956646/

首先，这道题状态压缩的方法很显然，但是状态太多了，会T（然而黄学长说：折半搜索也可过QAQ）
然后开始想高斯消元。一开始不知道高斯消元能解异或方程组，于是想了两个多小时QAQ
然后去补了解异或方程组，一开始对自由元的理解有问题，正确的应该是：
自由元可以随便定，每一组不同的自由元可以导出一组方程的解
换一句话说，消完元之后，非自由元的未知数的解，并非最终解

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 50;
const int INF = 50;

int n,m,vout=INF;
int mat[MAXN][MAXN],tag[MAXN];

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline void Gauss(){
	for (int k=1,w=k;k<n;w=++k){
		for (int i=k+1;i<=n&&!mat[k][w];i++) if (mat[k][i]) w = i;
		for (int i=1;i<=n+1;i++) swap(mat[i][w],mat[i][k]);
		for (int i=k+1;i<=n;i++) if (mat[k][i]) 
			for (int j=1;j<=n+1;j++) mat[j][i] ^= mat[j][k];
	}
}

void DFS(int w, int cost){
	if (cost >= vout) return;
	else if (!w) vout = min(vout, cost);
	else {
		if (mat[w][w]) {
			int t = mat[n+1][w];
			for (int i=w+1;i<=n;i++)
				if (mat[i][w]) t ^= tag[i];
			tag[w] = t;
			DFS(w-1, cost+(t?1:0));
		} else {
			tag[w] = 1;
			DFS(w-1, cost+1);
			tag[w] = 0;
			DFS(w-1, cost);
		}
	}
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) 
		mat[i][i] = 1, mat[n+1][i] = 1;
	for (int i=1,a,b;i<=m;i++){
		a = read(); b = read();
		mat[a][b] = mat[b][a] = 1;
	}
	Gauss(); 
	DFS(n,0);
	printf("%d\n",vout);
	return 0;
}