好吧好久没写，果然变懒了 = = 简略点好了
N x N 方阵，左上角入，左下角出，只能上下左右相邻移动，每格仅访问一次遍历所有格，求遍历方法数。
暴力 + 剪枝，没想出什么别的方法。最多就位运算优化一下：
Test 1: TEST OK [0.000 secs, 2900 KB] Test 2: TEST OK [0.000 secs, 2900 KB] Test 3: TEST OK [0.000 secs, 2900 KB] Test 4: TEST OK [0.000 secs, 2900 KB] Test 5: TEST OK [0.000 secs, 2900 KB] Test 6: TEST OK [0.000 secs, 2900 KB] Test 7: TEST OK [0.162 secs, 2900 KB] All tests OK.
N = 7 的时候在 0.162 秒貌似还不错，嗯。
代码嘛……算了不贴了。在 wordpress 上贴代码各种麻烦。研究一下再说
class farm{
int cnt, cowat[16], cowleft[5];
bool nochange[16];
unsigned long long ajtcnt[5];
const unsigned long long mask, maskl, maskr;
pair<int, int> putorder[16];
int dfscow[16], dfspos[16];
void addcow(int cowidx, int posidx){
switch(posidx){
/*
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
*/
case 0:
case 4:
ajtcnt[cowidx] += maskl >> (5 – posidx) * 4;
break;
case 3:
ajtcnt[cowidx] += maskr >> (5 – posidx) * 4;
break;
case 1:
case 2:
ajtcnt[cowidx] += mask >> (5 – posidx) * 4;
break;
case 5:
case 6:
case 9:
case 10:
case 13:
case 14:
ajtcnt[cowidx] += mask << (posidx – 5) * 4;
break;
case 8:
case 12:
ajtcnt[cowidx] += maskl << (posidx – 5) * 4;
break;
case 7:
case 11:
case 15:
ajtcnt[cowidx] += maskr << (posidx – 5) * 4;
break;
}
cowat[posidx] = cowidx;
}
int replace(int newcow, int posidx){
int oldcow = cowat[posidx];
unsigned long long m;
switch(posidx){
case 0:
case 4:
m = maskl >> (5 – posidx) * 4;
ajtcnt[newcow] += m;
ajtcnt[oldcow] -= m;
break;
case 3:
m = maskr >> (5 – posidx) * 4;
ajtcnt[newcow] += m;
ajtcnt[oldcow] -= m;
break;
case 1:
case 2:
m = mask >> (5 – posidx) * 4;
ajtcnt[newcow] += m;
ajtcnt[oldcow] -= m;
break;
case 5:
case 6:
case 9:
case 10:
case 13:
case 14:
m = mask << (posidx – 5) * 4;
ajtcnt[newcow] += m;
ajtcnt[oldcow] -= m;
break;
case 8:
case 12:
m = maskl << (posidx – 5) * 4;
ajtcnt[newcow] += m;
ajtcnt[oldcow] -= m;
break;
case 7:
case 11:
case 15:
m = maskr << (posidx – 5) * 4;
ajtcnt[newcow] += m;
ajtcnt[oldcow] -= m;
break;
}
cowat[posidx] = newcow;
return oldcow;
}
bool putable(int cowidx, int posidx) const {
return !((ajtcnt[cowidx] >> posidx*4) & 0xF);
}
void dfs(int idx){
int oldcow;
if(idx == 16){
if(!(cnt++)){
for(int i = 0; i < 16; ++i)
putorder[i] = make_pair(dfscow[i], dfspos[i]);
}
return;
}
int &cow(dfscow[idx]), &pos(dfspos[idx]);
for(cow = 0; cow < 5; ++cow)if(cowleft[cow]){
—cowleft[cow];
for(pos = 0; pos < 16; ++pos)if(nochange[pos] && putable(cow, pos)){
nochange[pos] = false;
oldcow = replace(cow, pos);
dfs(idx + 1);
replace(oldcow, pos);
nochange[pos] = true;
}
++cowleft[cow];
}
}
public:
template<class Iter>
farm(Iter beg, Iter end): cnt(0), mask (0x011101110111ULL),
maskl(0x011001100110ULL), maskr(0x001100110011ULL){
fill_n(ajtcnt, 5, 0);
fill_n(cowleft, 5, 3);
fill_n(nochange, 16, true);
for(int i=0; beg != end; ++beg, ++i)
addcow(*beg – ‘A’, i);
}
void calput(void){
int oldcow, &pos(dfspos[0]);
dfscow[0] = 3;
for(pos = 0; pos < 16; ++pos)if(putable(3, pos)){
nochange[pos] = false;
oldcow = replace(3, pos);
dfs(1);
replace(oldcow, pos);
nochange[pos] = true;
}
}
ostream& output(ostream& os){
for(int i=0; i<16; ++i){
div_t pos = div(putorder[i].second, 4);
os << char(putorder[i].first + ‘A’) << ‘ ‘
<< pos.quot + 1 << ‘ ‘ << pos.rem + 1 << ‘\n’;
}
os << cnt << ‘\n’;
return os;
}
};
int main(){
ifstream fin("wissqu.in");
farm wissqu((istream_iterator<char>(fin)), istream_iterator<char>());
fin.close();
ofstream fout("wissqu.out");
wissqu.calput();
wissqu.output(fout);
fout.close();
}
一个农场有很多块牧场(<=800)，这些牧场间有很多条(<=1450)道路相连，一些牛分散在这些牧场中。在这些牧场中寻找一个牧场，使得所有的牛到达该牧场所走的路程和最小，当然牛牛们会自己寻找到达该牧场的最短路径。
题目意图很明确，显然需要寻找每两个牧场间的最短路径，自然想到Floyd算法。不过该算法时间复杂度为O(V^3)，对此题来说就是 800*800*800=512000000，超时是必然的。之后就可以考虑 Heap 优化的 Dijkstra 算法和 SPFA 算法了。此题中是稀疏图，考虑先用一下 SPFA 看看情况。
const int infinite=1000000000;
int nCow,nPasture,nConnect;
vector<int> vCowsAt;
vector< list< pair<int,int> > > vPasAjt;
inline bool relax(int u, int v, int weight, vector<int> &d){
int newlength=d[u]+weight;
if(newlength<d[v]){
d[v]=newlength;
return true;
}
return false;
}
int CalPathSum(int iSource){
queue<int> Q;
vector<bool> IsInQ(nPasture);
vector<int> d(nPasture,infinite);
d[iSource]=0;
Q.push(iSource);
IsInQ[iSource]=true;
while(!Q.empty()){
int u=Q.front();
Q.pop();
IsInQ[u]=false;
for(list< pair<int,int> >::iterator itr=vPasAjt[u].begin();itr!=vPasAjt[u].end();++itr){
int v=itr->first;
if(relax(u,v,itr->second,d) && !IsInQ[v]){
Q.push(v);
IsInQ[v]=true;
}
}
}
int sum=0;
for(int i=0;i<nCow;++i)sum+=d[vCowsAt[i]];
return sum;
}
int main(){
ifstream fin("butter.in");
ofstream fout("butter.out");
fin>>nCow>>nPasture>>nConnect;
vCowsAt.resize(nCow);
vPasAjt.resize(nPasture);
for(int i=0;i<nCow;++i){
int iPasture;
fin>>iPasture;
vCowsAt[i]=iPasture-1;
}
for(int i=0;i<nConnect;++i){
int u,v,distance;
fin>>u>>v>>distance;
vPasAjt[u-1].push_back(pair<int,int>(v-1,distance));
vPasAjt[v-1].push_back(pair<int,int>(u-1,distance));
}
int minpath=infinite;
for(int i=0;i<nPasture;++i)
minpath=min(minpath,CalPathSum(i));
fout<<minpath<<endl;
}
果然不错，一次就通过了：
TASK: butter
